One hundred identical tennis balls are to be distributed among 10 children. In how many ways can this be done so that no child gets more than 20 balls

Question

One hundred identical tennis balls are to be distributed among 10 children. In how many ways can this be done so that no child gets more than 20 balls.

So what I got so far is that we need to subtract the bad distributions from the total amount of ways and the bad distributions would be giving each kid 21 balls or more so starting we have $\binom{100 +10-1}{100} - \left({4}\times {10\times\binom{79+10-1}{79}} - \binom{10}{2} \times\binom{58+10-1}{58}\right)$ however I have no idea where to go from here

Answer 1

As you determined, the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} = 100 \tag{1}$$ has $$\binom{100 + 10 - 1}{10 - 1} = \binom{109}{9}$$ solutions. From these, we must exclude those cases in which one or more of the variables exceeds $20$. Observe that at most four of the variables can exceed $20$ since $5 \cdot 21 = 105 > 100$.

Suppose $x_1 > 20$. Then $x_1' = x_1 - 21$ is a nonnegative integer. Substituting $x_1' + 21$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 21 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 100\\ x_1' + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 79 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{79 + 10 - 1}{10 - 1} = \binom{88}{9}$$ solutions. By symmetry, the same number of impermissible solutions occur for each of the ten variables. Hence, there are $$\binom{10}{1}\binom{88}{9}$$ solutions in which one of the variables exceeds $20$.

However, if we subtract $\binom{10}{1}\binom{88}{9}$ from $\binom{109}{9}$, we will have subtracted too much since we have counted solutions in which two variables exceed $20$ twice, once for each way of designating one of the variables as the one that exceeds $20$. Hence, we must add the number of solutions in which two of the variables exceed $20$.

Suppose $x_1, x_2 > 20$. Let $x_1' = x_1 - 21$ and $x_2' = x_2 - 21$. Then $x_1'$ and $x_2'$ are nonnegative integers. Substituting $x_1' + 21$ for $x_1$ and $x_2' + 21$ for $x_2$ in equation 1 yields \begin{align*} x_1' + 21 + x_2 + 21 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 100\\ x_1' + x_2' + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 58 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with

$$\binom{58 + 10 - 1}{10 - 1} = \binom{67}{9}$$

solutions. By symmetry, there are an equal number of solutions for each of the $\binom{10}{2}$ cases in which two of the variables exceed $20$. Hence, there are

$$\binom{10}{2}\binom{67}{9}$$

cases in which two of the variables exceed $20$.

Thus far, we have $\binom{109}{9} - \binom{10}{1}\binom{88}{9} + \binom{10}{2}\binom{67}{9}$. However, we have not excluded those cases in which three of the variables exceed $20$ since we subtracted them $\binom{3}{1} = 3$ times when we excluded cases in which one of the variables exceeds $20$ and added them $\binom{3}{2} = 3$ times when we included cases in which two of the variables exceed $20$. Thus, we must subtract them from the total.

Suppose $x_1, x_2, x_3 > 20$. Then $x_1' = x_1 - 21$, $x_2' = x_2 - 21$, and $x_3' = x_3 - 21$ are nonnegative integers. Substituting $x_1' + 21$ for $x_1$, $x_2' + 21$ for $x_2$, and $x_3' + 21$ for $x_3$ in equation 1 yields \begin{align*} x_1' + 21 + x_2' + 21 + x_3' + 21 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 100\\ x_1' + x_2' + x_3' + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 37 \tag{4} \end{align*} Equation 4 is an equation in the nonnegative integers with

$$\binom{37 + 10 - 1}{10 - 1} = \binom{46}{9}$$

solutions. By symmetry, there are equal number of solutions for each of the $\binom{10}{3}$ ways in which three of the variables could exceed $20$. Hence, there are

$$\binom{10}{3}\binom{46}{9}$$

cases in which three of the variables exceed $20$.

Thus far, we have $\binom{109}{9} - \binom{10}{1}\binom{88}{9} + \binom{10}{2}\binom{67}{9} - \binom{10}{3}\binom{46}{9}$. However, we have subtracted too much. We subtracted cases in which four of the variables exceed $20$ $\binom{4}{1} = 4$ times when we excluded those cases in which one of the variables exceeds $20$, added them $\binom{4}{2} = 6$ times when we included those cases in which two of the variables exceed $20$, and subtracted them $\binom{4}{3} = 4$ times when we excluded those cases in which three of the variables exceed $20$. Since we only want to exclude them once, we must add them back.

Suppose $x_1, x_2, x_3, x_4 > 20$. Let $x_1' = x_1 - 21$, $x_2' = x_2 - 21$, $x_3' = x_3 - 21$, and $x_4' = x_4 - 21$. Substituting $x_1' + 21$ for $x_1$, $x_2' + 21$ for $x_2$, $x_3' + 21$ for $x_3$, and $x_4' + 21$ for $x_4$ in equation 1 yields \begin{align*} x_1' + 21 + x_2' + 21 + x_3' + 21 + x_4' + 21 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 100\\ x_1' + x_2' + x_3' + x_4' + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} & = 16 \tag{5} \end{align*} Equation 5 is an equation in the nonnegative integers with

$$\binom{16 + 10 - 1}{10 - 9} = \binom{25}{9}$$

solutions. By symmetry, there are an equal number of solutions for each of the $\binom{10}{4}$ ways four of the variables could exceed $20$. Hence, the number of solutions in which four of the variables exceed $20$ is

$$\binom{10}{4}\binom{25}{9}$$

By the Inclusion-Exclusion Principle, the number of solutions of equation 1 in which none of the variables exceeds $20$ is

$$\binom{109}{9} - \binom{10}{1}\binom{88}{9} + \binom{10}{2}\binom{67}{9} - \binom{10}{3}\binom{46}{9} + \binom{10}{4}\binom{25}{9}$$

Answer 2

We can also do it by generating function.

The generating function for the same is $(1+x+x^2+.. + x^{20})^{10}$ and what we want is the coefficient of $x^{100}$.

$(1+x+x^2+.. + x^{20})^10 = (1-x^{21})^{10}.\frac{1}{(1-x)^{10}}$

$(1-x^{21})^{10}$ can be expressed $(1-{10\choose1}x^{21} + {10\choose2}x^{42}-{10\choose3}x^{63}+{10\choose4}x^{84}+...)$

$\frac{1}{(1-x)^{10}} = \sum_{0}^{\infty} {(n+10-1)\choose(10-1)}x^n$

$\frac{1}{(1-x)^{10}} = \sum_{0}^{\infty} {(n+9)\choose(9)}x^n$

Multiplying these two expressions, you are looking to have n+9-r where r is the reducing number from the first expression. $r_i = 0, 21, 42, 63, 84 for i = 0,1,2,3,4 respectively$

Thus coefficients are products of $(-1)^i({10\choose i}{(100+9-r_i)\choose 9}) x^{100}$

you get ${(100+9)\choose(9)}$ for the first term

you get the next one $- {10\choose1}{(100+9-21)\choose(9)}$

and the next one ${10\choose2}{(100+9-42)\choose(9)}$

Add these products such as below

$ {(100+9)\choose(9)}- {10\choose1}{(100+9-21)\choose(9)}+ {10\choose2}{(100+9-42)\choose(9)} - {10\choose3}{(100+9-63)\choose(9)} + {10\choose4}{(100+9-84)\choose(9)}$

Now add these

$ {(109)\choose(9)}- {10\choose1}{88\choose(9)}+ {10\choose2}{67\choose(9)} - {10\choose3}{46\choose(9)} + {10\choose4}{25\choose(9)}$ =$342,237,634,221$