Counting method for arrangements/selections

Question

What is the probability that a random arrangement of a deck of $52$ cards has exactly $k$ runs of hearts. (A run is a consecutive set ($1$ or more) of the same digit; e.g., $0001110100$ has three runs of $0$s.)

So my strategy, as usual, for these types of problems was to find number of desired outcomes divided by total possible outcomes. For desired number of outcomes, I reasoned it was $\binom{13-1}{k-1}$. I can't, however, figure out the total number of outcomes correctly. I thought it was simply $\sum_{k=1}^{13} \binom{13-1}{k-1}$, but the correct solution looks much different.

Assuming the desired number of outcomes is correct, how do you obtain the total number of possible outcomes? Or is there a better way of approaching this problem?

Answer 1

There are $\binom{13-1}{k-1}$ ways to decide how many hearts are to be in each run. Now you have to distribute the remaining $39$ cards in the $k+1$ slots determined by the runs, $k-1$ of them between runs, one before the first run, and one after the last run. The first and last slots can be empty, but each of the other $k-1$ must contain at least one card. Pretend that you have $39+2=41$ cards left to distribute, and each slot must get at least one; then they can be distributed in $\binom{41-1}{(k+1)-1}=\binom{40}k$ ways. Finally, the hearts can be permuted in $13!$ ways within their assigned places, and the other $39$ cards can be permuted in $39!$ ways in theirs, so I count

$$\binom{12}{k-1}\binom{40}k13!39!$$

desired permutations. There are $52!$ permutations altogether, so ... ?

As a quick check,

$$\sum_{k=0}^{13}\binom{12}{k-1}\binom{40}k13!39!=13!39!\sum_{k=0}^{13}\binom{12}{13-k}\binom{40}k\overset{*}=13!39!\binom{52}{13}=52!\;,$$

just as it should. The starred step uses Vandermonde’s identity.