# The Perfect Shuffle

Back to miscellaneous math pages

An ordering of cards in a deck is called a perfect shuffle if no card appears next to a card of the same number (cf. Sean).
The problem of finding the probability of a perfect shuffle is perhaps the most important open question in all of mathematics.

Update 1: The solution has been found. The following is an paraphrase from section 6 of this paper.
Let $$\Phi$$ be the linear functional defined by $$\Phi\left(x^n\right) = n!$$ and let $$l_n^*(x)$$ be the polynomial given by $$l_0^*(x)=1$$ and for $$n>0$$, $$l_n^*(x) = \sum_{k=0}^{n-1} \left(-1\right)^k \binom{n}{k} \binom{n-1}{k} k! \, x^{n-k} .$$ Then $$\Phi \left( \prod_{i=1}^r l_{n_i}^*(x) \right)$$ is the number of linear arrangements of $$n_1 + \dotsb + n_r$$ objects, with $$n_i$$ of color $$i$$, such that adjacent objects have different colors.
In particular, taking $$r = 13$$ and $$n_i = 4$$ for each $$i$$, we see that $$\Phi \left( \left( l_4^*(x) \right)^{13} \right) = 3668033946384704437729512814619767610579526911188666362431432294400$$ is the number of shuffles of a standard 52-card deck which are perfect shuffles. Thus the probability of a perfect shuffle is $$\frac{\Phi \left( \left( l_4^*(x) \right)^{13} \right)}{52!} = \frac{672058204939482014438623912695190927357}{14778213400262135041705388361938994140625} \approx 0.045476282331.$$ Thanks to Vatsa for finding the source.

Update 2: James wrote a nice paper, which can be found here, that explains the above result.