Deal 13 from Deck of Cards

If I were to deal 13 cards from a shuffled (presumed random) deck of cards, how many different ranks should I expect to see?

Suited89

After some serious number crunching, I get 188,474 / 20,825, which is about 9.05.

Quote: ThatDonGuy

After some serious number crunching, I get 188,474 / 20,825, which is about 9.05.

I agree. Using a Markov Chain, here is the average number after 1 to 52 cards.

Cards	Exp Ranks
1	1.00000000000000
2	1.94117647058824
3	2.82588235294118
4	3.65642256902761
5	4.43505402160864
6	5.16398559423769
7	5.84537815126050
8	6.48134453781513
9	7.07394957983193
10	7.62521008403361
11	8.13709483793517
12	8.61152460984394
13	9.05037214885954
14	9.45546218487395
15	9.82857142857143
16	10.17142857142860
17	10.48571428571430
18	10.77306122448980
19	11.03505402160860
20	11.27322929171670
21	11.48907563025210
22	11.68403361344540
23	11.85949579831930
24	12.01680672268910
25	12.15726290516210
26	12.28211284513810
27	12.39255702280910
28	12.48974789915970
29	12.57478991596640
30	12.64873949579830
31	12.71260504201680
32	12.76734693877550
33	12.81387755102040
34	12.85306122448980
35	12.88571428571430
36	12.91260504201680
37	12.93445378151260
38	12.95193277310920
39	12.96566626650660
40	12.97623049219690
41	12.98415366146460
42	12.98991596638660
43	12.99394957983190
44	12.99663865546220
45	12.99831932773110
46	12.99927971188480
47	12.99975990396160
48	12.99995198079230
49	13.00000000000000
50	13.00000000000000
51	13.00000000000000
52	13.00000000000000

9.05 is about 69.6% of the 13 ranks appearing.

If you take this same problem but assume infinite deck, I believe the answer is 1 - 1/e =~ 63.2% as the number of ranks approaches infinity. For instance, if you assume 1,000 ranks and draw 1,000 cards, the average number of ranks appearing is very close to 632.

I got this via simulation. Assuming it’s correct, can any of our calculus gurus get to the answer directly? I imagine the solution being an infinite series using inclusion-exclusion that turns out being an expression of 1/e...sort of like the derangement formula

Quote: Wizard

I agree. Using a Markov Chain...

My method:
First, determine all of the partitions of 13 such that no partition has more than 4 in it. This represents how many cards of particular ranks are in the hand.
For example, (4, 3, 3, 3) is a four of a kind and three threes of a kind, and (2, 2, 2, 1, 1, 1, 1, 1, 1, 1) are three pairs and seven singles.

Take (4, 3, 2, 2, 1, 1) as an example.
There are 13 possible choices for the four of a kind rank.
For each one, there are 12 possible choices for the three of a kind rank, and for each one, there are four possible threes (for example, three Aces could be Ace of spades, hearts, and clubs, Ace of spades, hearts, and diamonds, Ace of spades, clubs, and diamonds, or Ace of hearts, clubs, and diamonds).
For each one of these, there are C(11,2) = 55 possible choices for the two pair ranks, and for each one, there are six possible pairs.
For each one of these, there are C(9,2) = 36 possible choices for the two single ranks, and for each one, there are four possible cards.
The total = 13 x 12 x 4 x 55 x 6 x 36 x 4 = 29,652,480 13-card hands.
The number of different ranks in each of these hands is 6.

For every possible partition (IIRC, there are 39 of them), multiply the number of hands by the number of different ranks, then sum these 39 numbers and divide by the total possible number of hands, which is C(52,13).

If you assume infinite deck, then the limit is indeed 1-1/e. I have a proof, but it is 3 pages long and too mathematical to include in a reply. If there is a way to attach a pdf, I am happy to share it with anyone who is interested.

Quote: GM

If you assume infinite deck, then the limit is indeed 1-1/e. I have a proof, but it is 3 pages long and too mathematical to include in a reply. If there is a way to attach a pdf, I am happy to share it with anyone who is interested.

I'm interested

Here is the link to the paper on my OneDrive. Delete the space after //
https:// 1drv.ms/b/s!AhDS5R4jVo9yk0SAPjJWg1Wf2ZxP?e=eZjpir

Quote: GM

I have tried to include a link to it on my OneDrive, but the system won't let me, not even as plain text. :(

New posters can’t post links until they have 20 posts. If you post it as a broken link it will appear.

I am quite confident that I have the answer for the general question when there are n ranks, k cards of each rank (so n=13, k=4 for a standard deck of playing cards) and we draw N cards, but I don't have a proof yet.

The expected number of different ranks is n(1-C(kn,N)/C(k(n-1),N)),
where C(r,s) denotes the binomial coefficient r choose s, the number of ways of choosing s different objects from a set of r objects if don't care about their order.

If n=N=13, k=4, then C(52,13)=635013559600, C(48,13)=192928249296, 1-192928249296/635013559600=14498/20825 and the expected number of different ranks is 13*14498/20825=188474/20825 in agreement with everybody else's calculations.

If we fix n=13, k=4 and let N vary, then my formula gives the numbers which are in the Wizard's table.

If we fix n and N, and let k tend to infinity, then the number of expected ranks tends to n(1-(1-1/n)^N), which is the answer in the infinite deck case.

If we fix k, and let N and n tend to infinity in such a way that N/n has a limit c, then expected number of ranks divided by n tends to 1-(1-(c/k))^k.

If k=4 and N=n, then this expression gives 1-(3/4)^4=175/256=0.68359375.

If k tends to infinity, then 1-(1-(c/k))^k tends to 1-1/e^c, which is the limit in the infinite deck case.

I now have a proof, the formula in my previous post is correct, it can be proved by a method similar to the infinite deck case, apply the inclusion-exclusion principle to get an expression for the probabibility of there being exactly m different ranks, manipulate the generating function, then differentiate it to get the expected value. The variance can also be calculated, it is
n*[C(k(n-1),N)-C(k(n-2),N)]/C(kn,N)+n^2*[C(k(n-2),N)*C(kn,N)-(C(k(n-1),N)^2)]/(C(kn,N))^2.
If n=N=13, k=4, this formula gives 517492639794/468808755625, about 1.10.

There is a question on StackExchange, search for "expected number of cards that have been drawn at least once" as I am unable to post the URL.
It asks about the number of different cards, rather than the number of different ranks, but it is equivalent to having an infinite deck with 52 ranks. The answer given there gives a much easier explanation for the formula, I thought that there must be a simpler proof. It is not clear to me if there also is a similarly simple proof for the finite deck case.