# Counting method for arrangements/selections

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?

-

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.

-
The trick you use to address the end slots, why does that work? And if you pretend you have $41$ cards, why do you permute $39$ cards instead? – AlanH Feb 4 '13 at 4:03
@Alan: You put one imaginary card into each end slot, and now you have $39$ real cards left to distribute the way you really wanted: at least one in each interior slot, possibly none in the end slots. You could just as well have imagined using $k-1$ cards to ensure that each interior slot had one and distributing $39-(k-1)=40-k$ cards among $k+1$ slots, allowing $0$ in any slot. Again you get $\binom{40-k+(k+1)-1}{(k+1)-1}=\binom{40}k$ arrangements. – Brian M. Scott Feb 4 '13 at 4:08
@Alan: The $41$ is just to get the counting of arrangements right; there are really only $39$ non-hearts to be permuted. Remember, in the counting of arrangements we’re considering the non-hearts to be indistinguishable, so we can assume that the imaginary ones go to the end slots: if they don’t, we just interchange cards that were assumed to be interchangeable in the first place. – Brian M. Scott Feb 4 '13 at 4:09