I have the following questions:
In how many ways can we put 8 identical balls into 5 drawers which are stacked one atop another such that the upper drawer will have at most 4 balls and every other drawer will have at most 3 balls?
So I can see this is an inclusion exclusion question. I know that without any constraints, the number of ways to put 8 identical balls into 5 drawers is equal to the number of solutions to $ x_1 + x_2 + x_3 + x_4 + x_5 = 8$, which is $_{8+5-1}C_8 = _{12}C_8 $.
How ever, I find it hard to define my sets for the inclusion exclusion part – I tried to distinguish between constraints but got lost. Can anyone point me in the right direction please?
So first I removed all the cases which violates the first constraint, that is at least 5 balls in the upper drawer, then I am left with 3 balls and 5 drawers, total of $_{(3+5-1)}C_3 = _7C_3$ options eliminated, now we have 460 options left.
For each of the 4 drawers I define $F_i$ as the case when the i'th drawer has at least 4 balls. For each one I am left with 4 balls and 5 drawers, so number of options are $_{4+5-1}C_5 = _8C_5$.
The intersection of $F_i\cap F_j$ is only one option – 4 in each drawer, and I have $_4C_2$ options for intersections. the rest are zero due to limited number of balls.
So I get:
$ 460 – ( 4 * {_8}C_5 – _4C_2 * 1) = 460 -4 * 56 + 6 = 242 $
When I check the final answers available to me it says 186..
Best Answer
You made your mistake in counting the number of cases that violate the restriction that the lower four drawers can contain at most three balls.
Let $x_i$ be the number of balls placed in drawer $i$, where we count from the top drawer down. Since eight balls are placed in the five drawers, $$x_1 + x_2 + x_3 + x_4 + x_5 = 8 \tag{1}$$ is an equation in the nonnegative integers. The restriction that at most four balls may be placed in the top drawer means $x_1 \leq 4$. The restriction that at most three balls may be placed in every other drawer means $x_2, x_3, x_4, x_5 \leq 3$.
A particular solution of equation 1 corresponds to the placement of $5 - 1 = 4$ addition signs in a row of eight ones. For instance, $$1 1 + 1 + 1 1 1 + + 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 1$, $x_3 = 3$, $x_4 = 0$, $x_5 = 2$. The number of such solutions is the number of ways we can place four addition signs in a row of eight ones which is $$\binom{8 + 5 - 1}{5 - 1} = \binom{12}{4}$$ since we must choose which four of the twelve positions required for eight ones and four addition signs will be filled with addition signs.
From these, we must count those cases that violate one or more of the restrictions. Let $A_i$ be the set of solutions in which the $i$th drawer has more than the permitted number of balls.
$|A_1|$: The top drawer is allowed to have at most four balls, so we must subtract those cases in which $x_1 \geq 5$. Suppose $x_1 \geq 5$. Then $x_1' = x_1 - 5$ is a nonnegative integer. Substituting $x_1' + 5$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 5 + x_2 + x_3 + x_4 + x_5 & = 8\\ x_1' + x_2 + x_3 + x_4 + x_5 & = 3 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{3 + 5 - 1}{5 - 1} = \binom{7}{4}$$ solutions.
$|A_2|$: The second drawer is allowed to have at most three balls, so we must subtract those cases in which $x_2 \geq 4$. then $x_2' = x_2 - 4$ is a nonnegative integer. Substituting $x_2' + 4$ for $x_2$ in equation 1 yields \begin{align*} x_1 + x_2' + 4 + x_3 + x_4 + x_5 & = 8\\ x_1 + x_2' + x_3 + x_4 + x_5 & = 4 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with $$\binom{4 + 5 - 1}{5 - 1} = \binom{8}{4}$$ solutions.
By symmetry, $$|A_2| = |A_3| = |A_4| = |A_5| = \binom{8}{4}$$
$|A_1 \cap A_2|$: It is not possible for both the restrictions $x_1 \leq 4$ and $x_2 \leq 3$ to be violated since we would require at least $5 + 4 = 9 > 8$ balls to be placed in the drawers.
By symmetry, $$|A_1 \cap A_2| = |A_1 \cap A_3| = |A_1 \cap A_4| = |A_1 \cap A_5| = 0$$
$|A_2 \cap A_3|$: The only way to violate both the restrictions $x_2 \leq 3$ and $x_3 \leq 3$ is to place four balls in each drawer, which can be done in one way.
By symmetry, $$|A_2 \cap A_3| = |A_2 \cap A_4| = |A_2 \cap A_5| = |A_3 \cap A_4| = |A_3 \cap A_5| = |A_4 \cap A_5| = 1$$
It is not possible to violate three or more restrictions at once since we only have eight balls and $3 \cdot 4 = 12 > 8$.
Hence, by the Inclusion-Exclusion Principle, the number of admissible ways to distribute the balls is $$\binom{12}{4} - \binom{7}{4} - \binom{4}{1}\binom{8}{4} + \binom{6}{1}\binom{4}{4} = 495 - 35 - 4 \cdot 70 + 6 \cdot 1 = 495 - 35 - 280 + 6 = 186$$