Distributing $60$ identical balls into $4$ boxes if each box gets at least $4$ balls, but no box gets $20$ or more balls

Question

How many different ways can the balls be placed if each box gets at least $4$ balls each, but no box gets $20$ or more balls?

I was thinking about finding all the possible ways which every box gets at least $4$ balls which would be $47\choose44$ ways $\rightarrow$ $16215$ ways. Then subtracting that number by the number of possible ways that a box could get 20 or more balls ($16215$ - $20$ or more balls possibilities). The thing is I don't know how to get the number of ways if a box gets $20$ or more balls. Any tips?

Answer 1

You are expected to use the inclusion-exclusion principle. Compute the number of ways to distribute the balls without restriction. Then choose a box to get at least $20$ (4 ways), put $20$ in it, and distribute the rest of the balls among all the boxes. Subtract these arrangements. You have subtracted the ones with $20$ balls in two different boxes twice, so add them back. Finally the ones that have $20$ in three boxes...

Answer 2

What you have done thus far is correct.

As you observed, after distributing four balls to each box, we are left with $60 - 4 \cdot 4 = 44$ balls to distribute. If we let $x_i, 1 \leq i \leq 4$, represent the number of additional balls we distribute to the $i$th box, then $$x_1 + x_2 + x_3 + x_4 = 44 \tag{1}$$ Equation 1 is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of $4 - 1 = 3$ addition signs in a row of $44$ ones. The number of such solutions is $$\binom{44 + 4 - 1}{4 - 1} = \binom{47}{3} = \binom{47}{44}$$ since we must choose which three of the $47$ positions required for $44$ ones and three addition signs will be filled with addition signs or, equivalently, which $44$ positions will be filled with ones.

From these, we must subtract those cases in which a box receives at least $20$ balls. Since four balls have already been placed in each box, that means we must subtract those cases in which at least $20 - 4 = 16$ additional balls are placed in a box. Since $3 \cdot 16 = 48 > 44$, at most two boxes could have at least $16$ additional balls placed in them.

There are four ways to select a box that will receive at least $16$ additional balls. Suppose it is the first box. Then $x_1' = x_1 - 16$ is a nonnegative integer. Substituting $x_1' + 16$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 16 + x_2 + x_3 + x_4 & = 44\\ x_1' + x_2 + x_3 + x_4 & = 28 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with

$$\binom{28 + 4 - 1}{4 - 1} = \binom{31}{3} = \binom{31}{28}$$

solutions. Therefore, there are

$$\binom{4}{1}\binom{31}{3}$$

solutions in which at least $16$ additional balls are placed in one of the boxes.

However, if we subtract this amount from the total, we will have subtracted too much since we will have subtracted each case in which two boxes contain at least $20$ balls twice, once for each way we could have designated one of the boxes as the box that receives at least $16$ additional balls. We only wish to subtract such cases once, so we must add them back.

Choose which two of the four boxes receive at least $16$ additional balls. Suppose they are boxes 1 and 2. Let $x_1' = x_1 - 16$; let $x_2' = x_2 - 16$. Then $x_1'$ and $x_2'$ are nonnegative integers. Substituting $x_1' + 16$ for $x_1$ and $x_2' + 16$ for $x_2$ in equation 1 yields \begin{align*} x_1' + 16 + x_2' + 16 + x_3 + x_4 & = 44\\ x_1' + x_2' + x_3 + x_4 & = 12 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with

$$\binom{12 + 4 - 1}{4 - 1} = \binom{15}{3} = \binom{15}{12}$$

solutions. Hence, there are

$$\binom{4}{2}\binom{15}{3}$$

solutions in which at least $16$ additional balls are placed in two of the boxes.

By the Inclusion-Exclusion Principle, the number of distributions of $60$ indistinguishable balls to four boxes in which each box receives at least four balls and no box receives at least $20$ balls is

$$\binom{47}{3} - \binom{4}{1}\binom{31}{3} + \binom{4}{2}\binom{16}{3}$$