Intereting Posts

with inequality $\frac{1}{3a+5b+7c}+\frac{1}{3b+5c+7a}+\frac{1}{3c+5a+7b}\le\frac{\sqrt{3}}{4}$
Short matrix algebra question
Metric Space and ordered field
How to do $\sum_{k=1}^{\infty} \frac{\cos(kx)}{k^2}$?
If the empty set is a subset of every set, why isn't $\{\emptyset,\{a\}\}=\{\{a\}\}$?
Congruence Relation with exponents and variables
Continuous Function
Probability of random integer's digits summing to 12
Why can't three unit regular triangles cover a unit square?
Bijection between $$ and $
A question comparing $\pi^e$ to $e^\pi$
Can a collection of points be recovered from its multiset of distances?
Let $N$ be a normal subgroup of index $m$ in $G$. Prove that $a^m \in N$ for all $a \in G$.
$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$ show that $x=-c/b$ when $a=0$
Number of invertible 0-1 matrices

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?**

- What is the math behind the game Spot It?
- What are the probabilities of getting a “Straight flush” in a poker game?
- Probability of having exactly 1 pair from drawing 5 cards
- Derangements with repetitive numbers
- Game Theory Matching a Deck of Cards
- In the card game “Projective Set”: Compute the probability that $n$ cards contain a set

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.

- Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
- number of subsets of even and odd
- Is there a memorable solution to Kirkman's School Girl Problem?
- Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$
- A neater solution to an interesting question part 2
- Ways of getting a number with $n$ dice, each with $k$ sides
- Are there arbitrarily large sets $S$ of natural integers such that the difference of each pair is their GCD?
- Can 12 teams in 6 disciplines play 6 rounds without repetition?
- A closed form for the sum of $(e-(1+1/n)^n)$ over $n$
- Number of ways to divide a stick of integer length $N$

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}
```

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.

- Characterisation of extreme mono- and epi- morphisms in category of topological spaces.
- Understanding how the rules of probability apply to probability density functions
- Classify orbits of conjugating action on $GL_2(\mathbb{C})$
- How do I integrate $\int_{0}^{1}\!\sin x^2\,dx$?
- Integrate $ \int_{0}^{\frac{\pi}{4}}\tan^{-1}\left(\frac{\sqrt{2}\cos3 \phi}{\left(2\cos 2 \phi+ 3\right)\sqrt{\cos 2 \phi}}\right)d\phi$
- What are the vertices of a regular tetrahedron embeded in a sphere of radius R
- Find all positive integers $a, b, c$ such that $a^2+1$ and $b^2+1$ are both primes and $(a^2+1)(b^2+1)=c^2+1$
- Good textbooks for lattice and coding theory
- Is $L^{p}$ space with alternate norm banach?
- The sum of a polynomial over a boolean affine subcube
- The contradiction method used to prove that the square root of a prime is irrational
- Eisenstein and Quadratic Reciprocity as a consequence of Artin Reciprocity, and Composition of Reciprocity Laws
- Minimize : $\sqrt{(1+{1\over a})(1+{1\over b})}$ subject to $a+b=\lambda$.
- There's non-Aleph transfinite cardinals without the axiom of choice?
- Solving for a variable that's an exponent