1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! Would you also happen to know how this relates to n-k + 1 choose k? Everything else is perfect, but I do not see how it relates. It does, however, give the same answer: 22 choose 5 as you mentioned. $\endgroup$ – 114 Mar 5 '13 at 16:51
  • $\begingroup$ @Stopwatch: If you have $n$ letters altogether, of which $k$ are vowels, you have $n-k$ balls, $k-1$ middle boxes, and $2$ end boxes. After you put one ball in each of the $k-1$ middle boxes you have $(n-k)-(k-1)=n-2k+1$ balls to distribute arbitrarily to $k+1$ boxes, and the stars-and-bars formula gives the result $\binom{(n-2k+1)+(k+1)-1}{(k+1)-1}=\binom{n-k+1}k$. $\endgroup$ – Brian M. Scott Mar 5 '13 at 17:05
  • $\begingroup$ Wonderful, so it really is a direct application of the argument above. Thank you again! $\endgroup$ – 114 Mar 5 '13 at 17:12
  • $\begingroup$ @Stopwatch: My pleasure! $\endgroup$ – Brian M. Scott Mar 5 '13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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