Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.