# How many ways are there to distribute 26 identical balls into six distinct boxes such that…

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?

## 3 Answers

Let me give you a hint for part (a).

You have 26 balls and 6 boxes, but you must put an odd number of balls in each box.

Start by putting one ball in each box: all boxes contain an odd number, and you are left with 20 balls.

Note that you have to do this eventually: you cannot leave a box with 0 balls.

You are now left with 20 balls, or rather 10 pairs of balls: and since adding a pair to a box leaves it odd-numbered, you can freely distribute the pairs in the boxes.

So: how many ways are there of distributing 10 pairs in 6 boxes?

First problem:

How many ways are there to distribute $26$ identical balls into six distinct boxes such that the number of balls in each box is odd?

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.

There are $$\binom{10 + 5}{5} = \binom{15}{5}$$ solutions since we must choose which five of the fifteen symbols (ten ones and five addition signs) will be addition signs.

Second problem:

How many ways are there to distribute $26$ identical balls into six distinct boxes such that the first three boxes contain at most six balls?

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

$$\binom{26 + 5}{5} = \binom{31}{5}$$

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

$$\binom{19 + 5}{5} = \binom{24}{5}$$

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

$$\binom{3}{1}\binom{24}{5}$$

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

$$\binom{12 + 5}{5} = \binom{17}{5}$$

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

$$\binom{3}{2}\binom{17}{5}$$

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

$$\binom{5 + 5}{5} = \binom{10}{5}$$

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

$$\binom{31}{5} - \binom{3}{1}\binom{24}{5} + \binom{3}{2}\binom{17}{5} - \binom{3}{3}\binom{10}{5}$$

• +1 very good answer for part (b). I particularly enjoyed how you explained how we got the binomial coefficients. – Kenneth Worden Mar 3 '17 at 0:11

distributing k identical balls in m differrent boxes that must contain an odd number of balls is equiavalent with a composition of k in m odd parts. number of compositions of k in m odd parts we count from formula $$c_m(k,O)=\binom{m+(k-m)/2-1}{(k-m)/2}$$ in our case $k=26,m=6$ $$c_6(26,O)=\binom{6+10-1}{10}=\binom{15}{10}$$