2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}$$

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

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.