Probability of getting A to K on single scan of shuffled deck

Let us say we have a regular 52-card well-shuffled deck.

We scan through the deck (first to last) till we find an Ace. Then we continue (from that Ace) till we find a 2. Then we scan (from the 2) till we find a 3, and so on. We stop when we find a King. (Suits don't matter.)

What is the probability that we can complete this process within one scan of the deck?

It seems an extremely hard question, and I haven't made any progress. I don't know if this has been answered elsewhere, if so, a link is enough.

Solution 1:

Let $$F(x):=x^{13}\cdot(\frac{(-x)^0}{3!}+\frac{(-x)^1}{2!}+\frac{(-x)^2}{1!}+\frac{(-x)^3}{0!})^{13}$$

Then $$4!^{13}\cdot\sum_{k=13}^{52} \frac{1}{k!}[x^k]F(x)=\frac{50972203946555791528902451677555189167087762981}{92024242230271040357108320801872044844750000000000} =0.000553899741\cdots$$

is the required probability.

Ignoring suits, the number of permutations of a deck is $\frac{52!}{4!^{13}}$.

Let $N$ be the number of permutations that we can complete this process.

$$X:=x_1+x_2+x_3+...+x_{13}$$ $$X^{\ast}:=X^{0}+X^{1}+X^{2}+...=(1-X)^{-1}$$

Then

$$N=[x_1^{4}{\cdot}x_2^{4}{\cdot}...{\cdot}x_{13}^{4}](X-x_1)^{\ast}{\cdot}x_1{\cdot}(X-x_2)^{\ast}{\cdot}x_2{\cdot}...{\cdot}(X-x_{13})^{\ast}x_{13}{\cdot}X^{*}$$

$$=[x_1^{3}{\cdot}x_2^{3}{\cdot}...{\cdot}x_{13}^{3}](1-X)^{-14}\prod_{i=1}^{13}(1+(1-X)^{-1}{\cdot}x_i)^{-1}$$

$$=[x_1^{3}{\cdot}x_2^{3}{\cdot}...{\cdot}x_{13}^{3}](1-X)^{-14}\prod_{i=1}^{13}(1+(-x_i)*(1-X)^{-1}+((-x_i)*(1-X)^{-1})^{2}+((-x_i)*(1-X)^{-1})^{3})$$

$$=\sum_{0{\le}k_1,k_2,...,k_{13}\le3}(-1)^{k_1}{\cdot}...{\cdot}(-1)^{k_{13}}[x_1^{3-k_1}{\cdot}...{\cdot}x_{13}^{3-k_{13}}](1-X)^{-k_1-...-k_{13}-14}$$

Here

$$[x_1^{3-k_1}{\cdot}...{\cdot}x_{13}^{3-k_{13}}](1-X)^{-k_1-...-k_{13}-14}=[x_1^{3-k_1}{\cdot}...{\cdot}x_{13}^{3-k_{13}}]\sum_{r{\ge}0}\binom{k_1+...+k_{13}+13+r}{r}X^{r}$$

$$=\binom{52}{39-(k_1+...+k_{13})}{\cdot}\frac{(39-(k_1+...+k_{13}))!}{(3-k_1)!{\cdot}...(3-k_{13})!}$$

$$=\frac{52!}{(13+k_1+k_2+...+k_{13})!}{\cdot}\frac{1}{(3-k_1)!{\cdot}...{\cdot}(3-k_{13})!}$$

Hence

$$N=\sum_{0{\le}k_1,k_2,...,k_{13}\le3}\frac{52!}{(13+k_1+k_2+...+k_{13})!}{\cdot}\frac{(-1)^{k_1}}{(3-k_1)!}{\cdot}\frac{(-1)^{k_2}}{(3-k_2)!}{\cdot}...{\cdot}\frac{(-1)^{k_{13}}}{(3-k_{13})!}$$

$$=52!\cdot\sum_{k=13}^{52} \frac{1}{k!}[x^k]F(x)$$

The required probability is $\frac{N}{\frac{52!}{4!^{13}}}$.

Reference: Combinatorial Enumeration by Ian P. Goulden & David M. Jackson, pages 73, 74.

Solution 2:

Here's a hands-on intuitive approach to the problem. Suppose we have an alphabet $\mathcal{A}=\{a_1,\ldots,a_k\}$. Given nonnegative integers $n_1,\ldots,n_k$ and $m_1,\ldots, m_k$, let $$\left[\begin{array}{c}n_1,\ldots,n_k\\m_1,\ldots,m_k\end{array}\right]$$ denote the number of words that can be formed from $n_i$ copies of $a_i$, such that the word contains, as a (possibly nonconsecutive) subsequence, a pattern containing exactly $m_i$ copies of the letter $a_i$. (The count is independent of which pattern is chosen.) Your problem is to compute $$\left[\begin{array}{c}4,\ldots,4\\ 1,\ldots,1\end{array}\right]$$ where there are 13 terms on both the top and bottom.

Some special cases are easy: if any $n_i$ or $m_i-n_i$ is negative, the count is zero, and if $k=0$ the count is $1$ (for the empty word). If $n_i=m_i$ for all $i$, then the count is $1$, since the pattern accounts for the entire word. Nontrivial values can be computed via two recursive rules:

The Zero Rule: If $m_i=0$ for some $i$, then $$\left[\begin{array}{c}n_1,\ldots,n_k\\m_1,\ldots,m_k\end{array}\right]= \binom{\sum n_j}{n_i}\left[\begin{array}{c}n_1,\ldots,\hat{n_i},\ldots,n_k\\m_1,\ldots,\hat{m_i},\ldots,m_k\end{array}\right]$$ where the hats indicate that $n_i$ and $m_i$ have been omitted. To see this, note that if $m_i=0$, the pattern doesn't actually involve the letter $a_i$, so the $a_i$'s can be placed arbitrarily; the binomial coefficient counts the ways to do that. As a special case, note that when $m_i=0$ for all $i$, the Zero Rule tells us that the count is a multinomial coefficient: $$\left[\begin{array}{c}n_1,\ldots,n_k\\ 0,\ldots,0\end{array}\right]=\binom{\sum_i n_i}{n_1,\ldots,n_k},$$ as expected since the pattern is empty, so every permutation of the letters matches.

The Peeling Rule: For any $j$, $1\le j \le k$, we can "peel off" the first letter of the word to get: $$\left[\begin{array}{c}n_1,\ldots,n_k\\m_1,\ldots,m_k\end{array}\right]= \sum_{i=1}^k \left[\begin{array}{c}n_1,\ldots,n_{i-1},n_i-1,n_{i+1},\ldots,n_k\\m_1,\ldots,m_{i-1},m_i-\delta_{ij},m_{i+1},\ldots, m_k\end{array}\right]$$ where as usual $\delta_{ij}$ is $1$ iff $i=j$. (To see this, we can assume the pattern starts with $a_j$. Consider all possibilities $a_i$ for the first letter in the word; it starts a pattern match iff $i=j$.)

To see that these rules suffice, note that peeling produces a sum of terms with strictly smaller $\sum n_i$. Finally, note that the count is unchanged if the same permutation is applied to the $n_i$'s and the $m_i$'s. While this doesn't make the expression simpler, it is useful when using dynamic programming to minimize the number of subexpressions that need to be evaluated. A straightforward Mathematica implementation verifies the excellent answer provided by @nczkxv.

> S[Array[4 &, 13], Array[1 &, 13]] // Timing
> {1.171875, 50972203946555791528902451677555189167087762981}