In general we state that there are ${r-wn – (n-1) \choose (n-1)}$ ways to distribute r identical balls in n distinct boxes with at least w balls in each box. Considering this, how many ways are there to arrange the 26 letters of the alphabet so that no two vowels are consecutive? I was able to obtain the answer by using the formula ${n-k + 1 \choose k}$ where there are k balls and n boxes but I have two issues:
1) I do not fully understand why this formula is equivalent to the one mentioned at the beginning of this question;
2) I am not sure how in a solution to this problem the answer ${21 – 4 + (6-1) \choose 6-1}$ was arrived at.
Could someone clarify how these all fit together? Thanks in advance!
Best Answer
First put $w$ balls in each of the $n$ boxes; that uses up $wn$ of the balls, leaving you $r-wn$ to distribute arbitrarily amongst the $n$ boxes. By the standard stars-and-bars argument, the number of ways to distribute $m$ indistinguishable balls amongst $n$ distinguishable boxes is
$$\binom{m+n-1}{n-1}\;,\tag{1}$$
and in this case $m=r-wn$, so in this case we get
$$\binom{r-wn+n-1}{n-1}\;.$$
(Note that you have a sign wrong in the expression at the beginning of your question.)
Now recall the identity $\binom{n}k=\binom{n}{n-k}$ and apply it to $(1)$ to get
$$\binom{m+n-1}{n-1}=\binom{m+n-1}m\;.\tag{2}$$
Thus, the righthand side of $(2)$ also gives the number of ways to distribute $m$ indistinguishable balls amongst $n$ boxes (and you have another sign error: your $n-k+1$ should be $n+k+1$). In the case $m=r-wn$ in which we start with the minimum of $w$ balls in each box, it becomes
$$\binom{r-wn+n-1}{r-wn}\;.$$
In the specific problem at hand, however, you can’t use either of these without some adjustment. You have $6$ boxes, namely, the $4$ slots between adjacent vowels and the slots on the two ends, and $21$ balls. Each of the $4$ boxes in the middle must receive at least one ball, but either or both of the end slots could be left empty. Thus, you should begin by putting one ball in each of the $4$ middle boxes, leaving $17$ balls to be distributed arbitrarily amongst the $6$ boxes. Either expression in $(2)$ can now be used: there are $$\binom{17+6-1}{6-1}=\binom{22}5=\binom{22}{17}=\binom{17+6-1}{17}$$ ways to distribute the consonants amongst the vowels, ignoring which consonant is which. Of course this must then be multiplied by $5!21!$ to account for the order of the vowels and consonants within their respective sets of positions in the string.