How many ways are there to distribute $26$ identical balls into $6$ distinct boxes such that:
(a) The number of balls in each box is odd
(b) The first three boxes contain at most $6$ balls each
I know how to write a generating function for both of these problems, but I don't know how to get an actual number for a specific problem.
For part (a), I can't come up with a closed form for a generating function to make each box have an odd number of balls.
Do I have to break part (b) into multiple cases, or is there an inclusion-exclusion trick to make it much more manageable?
Best Answer
First problem:
Let $x_k$ denote the number of balls placed in the $k$th box, $1 \leq k \leq 6$. Then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 26 \tag{1}$$ Since each $x_k$ is a positive odd integer, $x_k = 2y_k + 1$ for some non-negative integer $y_k$. Substituting into equation 1 and simplifying yields $$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 10 \tag{2}$$ which is an equation in the non-negative integers. The number of solutions of equation 2 is the number of ways five addition signs can be inserted into a row of ten ones.
Second problem:
We wish to solve the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 26 \tag{3}$$ in the non-negative integers subject to the constraints that $x_1, x_2, x_3 \leq 6$. Equation 3 is an equation in the non-negative integers. It has
solutions.
We must exclude those cases in which one or more of the constraints is violated.
Suppose the constraint $x_1 \leq 6$ is violated. Then $x_1 \geq 7$. Let $y_1 = x_1 - 7$. Then $y_1$ is a non-negative integer. Substituting $y_1 + 7$ for $x_1$ in equation 3 and simplifying yields $$y_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 19 \tag{4}$$ Equation 4 is an equation in the non-negative integers. It has
solutions. By symmetry, equation 3 has the same number of solutions if the constraint $x_2 \leq 6$ or the constraint $x_3 \leq 6$ is violated. Hence, there are
solutions in which one of the constraints is violated.
Suppose the constraints $x_1 \leq 6$ and $x_2 \leq 6$ are both violated. Let $y_1 = x_1 - 7$; let $y_2 = x_2 - 7$. Then $y_1$ and $y_2$ are non-negative integers. Substituting $y_1 + 7$ for $x_1$ and $y_2 + 7$ for $x_2$ and simplifying yields $$y_1 + y_2 + x_3 + x_4 + x_5 + x_6 = 12 \tag{5}$$ which is an equation in the non-negative integers with
solutions. By symmetry, equation 3 has the same number of solutions if both the constraints $x_1 \leq 6$ and $x_3 \leq 6$ are violated or both the constraints $x_2 \leq 6$ or $x_3 \leq 6$ are violated. Hence, there are
solutions in which two of the constraints are violated.
Suppose that all three constraints are violated. Let $y_k = x_k - 7$, $1 \leq k \leq 3$. Then each $y_k$ is a non-negative integer. Substituting $y_k + 7$ for $x_k$, $1 \leq k \leq 3$, and simplifying yields $$y_1 + y_2 + y_3 + x_4 + x_5 + x_6 = 5 \tag{6}$$ which is an equation in the non-negative integers with
solutions.
By the Inclusion-Exclusion Principle, the number of ways the $26$ identical balls can be distributed into six distinct boxes such that the first three boxes contain at most six balls is