Calculating card deck shuffling odds

Question

Start with a standard deck of 52 cards in some known order; each card can be tagged with its ordinal position in the deck.

Then apply a random shuffling algorithm (i.e. Knuth's shuffle).

After the shuffle, it is possible for one or more cards to end up in the same ordinal position where they were before the shuffle -- i.e. the shuffle did not move them. How can I calculate the probability of this occurring based on the number of unmoved cards?

In other words, calculate P(n) as the probability that, after the shuffle, at least n cards have not moved.

Answer 1

I will give a brief answer, you can find the full solution there (along with additional stuff). In what follows I will use $n$ for the sake of generality (you will see that it does not matter a lot actually), but in the case of a deck of card, you can replace it by 52 everywhere.

If we assume that your shuffling algorithm amounts to selecting one permutation at random, we need to count permutations. There are $n!$ permutations of the deck. The number of derangements (permutations where no card ends up in the same position) is

$$ n!\sum_{i=0}^n\frac{(-1)^i}{i!}.$$

The number of permutations where exactly $k$ cards end up at the same position is the product of the number of derangements of $n-k$ cards and the number of ways of choosing $k$ cards among $n$:

$$ {n \choose k} (n-k)! \sum_{i=0}^{n-k}\frac{(-1)^i}{i!}.$$

Finally, the probability of such a permutation is

$$ \frac{1}{k!} \sum_{i=0}^{n-k}\frac{(-1)^i}{i!} \approx \frac{e^{-1}}{k!}.$$

In the last approximation, we used the first terms of the series development of $e^x$. Interestingly, we recognize the Poisson distribution with parameter $\lambda = 1$, and we see that this approximation does not depend on $n$. So the distribution of the number of fixed cards (not their proportion) rapidly converges to a constant distribution.