# Probability of finding a complete deck of cards in random shuffle of $n$ such decks?

I asked this question on Reddit, and it was suggested I might get direction here.

If I take a deck of cards, with $k$ cards in it (all distinct), and shuffle together $n$ exact copies of that initial deck (consider it a random permutation of the $n*k$ cards), what is the probability that if I go through the whole shuffled $n*k$ cards, I'll find at least one complete set of the $k$ distinct cards in $k$ consecutive positions?

For example, if the initial deck was $1,2,3$ and I shuffled 5 copies (so 15 cards total), the probability I find $1,2,3$ or $2,1,3$ or any other permutation of the basic deck in any three consecutive positions in the 15 card combined and shuffled deck?

I was able to get the case for the first $k$ cards containing the complete initial deck of $k$ cards, but I'm stumped covering the any $k$ consecutive positions case.

• I think that an exact expression may be very difficult to get at. But it should not be too bad to find the expected number of full decks one will get. – André Nicolas Jun 2 '16 at 20:33

You start at a random position that has k-1 or more cards following. You pick one card, then you need to pick k-1 more cards, each not matching a card that you picked before.

For the second card you pick, there are nk - 1 cards you could pick, and n (k-1) that are not the same as the one you picked first. For the third card, there are nk - 2 cards you could pick, and n (k-2) are not the same as the first two you picked. And so on. When you pick the k-th card, there are nk - (k-1) that you could pick, and only n that don't match one of the cards before.

You multiply all the (number of Ok choices), and divide by all the (number of possible choices). The product of all the (number of Ok choices) is $n^{k-1} (k-1)!$. The product of all the (possible choices) is $(nk - 1)! / (nk - k)!$. Dividing gives $n^{k-1} (k-1)! (nk - k)! / (nk - 1)!$, which is the same as $n^k k! (nk - k)! / (nk)!$ (multiply numerator and denominator by nk).

we need to draw k cards from $n*k$ cards. first card can be anything because we dont have any card till now so whatever we get it is needed to complete the k distinct deck of cards.

probability for drawing 1 distinct card is 1


now we draw the second card from $n*k-1$ out of these we dont desire n-1 cards which have the same face as the first card we drew so.

probability of drawing second card is


$$(n*k-1-(n-1))/(n*k-1) =n*(k-1)/(n*k-1)$$

for third card we have to draw from $n*k-2$ cards and we have $(n*k-2)-2*(k-2)$ favourable cases

probability of drawing thrid card is


$$(n*k-2-2*(n-1))/(n*k-2) = n*(k-2)/(n*k-2)$$

see the pattern

probability for $i^{th}$ draw is $$(n*k-(i-1)-(i-1)*(n-1))/(n*k-2) = n*(k-(i-1))/(n*k-(i-1))$$

and our answer is the multiplication of these all from i=1 to i=k

$$\prod_{i=1}^k n*(k-(i-1))/(n*k-(i-1))=n^k*k!*{k(n-1)}! / {nk}!$$

• yeah sorry calculation mistake – Nikhil Jun 2 '16 at 20:06