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.