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.