Proving Probability: Solutions to x_1+...+x_r=n with k Zero Terms

[quasar987]

Show that there are $\binom{r}{k}\binom{n-1}{n-r-k}$ solutions to the equation $x_1+...+x_r=n$ for which exactly k of the r terms of the sum are nul.

There are $\binom{r}{k}$ ways of choosing which k of the r $x_i$'s are zero, and there are

$$\binom{n+(r-k)-1}{n}$$

distinc solutions to the resulting equation. What is wrong with that? If nothing, how are the two binomial coefficients equal?

 

[0rthodontist]

It says exactly k must be null. So once you've chosen your 0's, the remaining variables must take values >= 1.

 

[AKG]

The whole thing doesn't look right. Treat the x_i as distinguishable boxes and n as a bunch of n indistinguishable balls. The question is, how many ways can you put n indistinguishable balls into r distinct boxes if exactly k of the r boxes end up empty?

There are $\binom{r}{k}$ ways to choose which boxes will be empty. Now put your n balls in a row, and observe there are n-1 gaps between adjacent balls. Pick r-k-1 of these gaps (there are $\binom{n-1}{r-k-1} = \binom{n-1}{(n-1)-(r-k-1)} = \binom{n-1}{n-(r-k)}$ ways to do this). The bunch of balls occurring before the first chosen gap goes in the first of the boxes that wasn't chosen to be empty. The next bunch of balls (occuring between the first and second chosen gaps) goes in the next of the boxes that wasn't chosen to be empty.

 

[quasar987]

Well spoted 0rthodontist. And AKG too for noticing that there is an error in the question. (the book really says n-r-k)