What is the number of ways to put 40 identical balls in 6 boxes while no box contains more than 14 balls.

Question

I believe that I have to use the Inclusion–exclusion principle but I am not sure how. I tried to use this formula: $\binom{n+k-1}{n-1}$ for every step of the inclusion–exclusion solution but it didn't work out. Thank you!!

Answer 1

Inclusion exclusion.

Include all of the ways to allocate 40 balls among the 6 boxed without restriction.

Exclude the cases that one box holds more than 14 balls... choose one box (how many ways can you do this?) Put 15 balls in that box. How many ways to allocate the remaining 25 balls (with the possibility that there are more than 15 balls in the over-filled box.)

Now you have double counted cases where two boxes have more than 14 balls. Include those boxes.

Choose 2 boxes, put 15 balls in each. Count the number of ways to allocate the rest.

${45\choose 5} - {6\choose 1}{30\choose 5} + {6\choose 2}{15\choose 5}$

Answer 2

Jack D'Aurizio gives the clue, it can be solved by using the generating functions. In this case, generating function is $$G(x) = (1+x+x^2+\ldots+x^{14})^6$$ and we are seeking the coefficient of $x^{40}$. Now, if we manipulate the expression by using: $$1+x+x^2+\ldots+x^{14} = \frac{1-x^{15}}{1-x}\ and\ \frac{1}{1-x} = 1+x+x^2+...$$ we get $$G(x) = (1-x^{15})^6 \cdot (1+x+x^2+...)^6$$ Now, we also know that we have $$(1+x+x^2+...)^6 = \sum_{m = 0}^{\infty}\binom{6+m-1}{6-1}x^m$$ So generating function becomes $$G(x) = (1-x^{15})^6 \cdot \sum_{m = 0}^{\infty}\binom{5+m}{5}x^m$$ So the coefficient of the term $x^{40}$ is: $$\binom{6}{0} \binom{45}{5}-\binom{6}{1}\binom{30}{5}+\binom{6}{2}\binom{15}{5}$$