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.

Solutions Collecting From Web of "Probability of getting A to K on single scan of shuffled deck"

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
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
\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:
\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}

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}

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.













$$=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.