20 identical balls, 4 distinct boxes

Question

In how many ways can 20 identical balls be distributed into 4 distinct boxes subject to the following conditions.

Each box gets an even number of balls.

I've made some code in python which gave me an answer of 286

I tried different methods to work this out mathematically and the only one that proved useful is:

2x + 2y + 2z + 2w = 20
x + y + z + w  = 10
С(10+3,10) = 286

But I don't understand why this works. Can anyone please give a mathematical solution to the problem?

Answer 1

Since the balls are indistinguishable, and you need to put an even number of them into each box, you might as well glue them together in pairs. Now you just want to know the number of ways to distribute these glued pairs amongst the four boxes. If you let $x,y,z$, and $w$ be the numbers of glued pairs in the four boxes, then clearly you must have $x+y+z+w=10$, and each of $x,y,z$, and $w$ must be a non-negative integer. Conversely, if you have four non-negative integers $x,y,z$, and $w$ whose sum is $10$, they give you a possible distribution of the glued pairs: $x$ in the first box, $y$ in the second box, and so on. Thus, the number of ways to distribute the glued pairs is the same as the number of solutions of $x+y+z+w=10$ in non-negative integers. This is a standard stars-and-bars problem, with (as you found) the solution

$$\binom{10+4-1}{4-1}=\binom{13}3=286\;.$$

The reasoning behind the this result is described quite well in the linked article, but I’ll repeat here the special case that you need.

Think of laying out the $10$ glued pairs in a row on the table:

$$\begin{array}{c}\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty\end{array}$$

They’re completely indistinguishable, so it doesn’t matter which one is which. Now insert three dividers to mark the breaks between the pairs in the first and second boxes, those in the second and third boxes, and those in the third and fourth boxes. For instance, if there are $3$ pairs in the first box, none in the second, $5$ in the third, and $2$ in the fourth, you get this arrangement:

$$\begin{array}{c}\infty&\infty&\infty&|&|&\infty&\infty&\infty&\infty&\infty&|&\infty&\infty\end{array}$$

In any such arrangement of pairs and dividers you have a string of $10+3=13$ objects. There are $\binom{13}3$ ways to pick the $3$ positions for the dividers, and each choice of positions for the dividers corresponds to exactly one of the possible distributions of the glued pairs. Conversely, each distribution can be represented by one of these arrangements of $10$ pairs and $3$ dividers. Thus, there are $\binom{13}3$ distributions of the glued pairs. And as we saw at the beginning, each of them corresponds to exactly one of the possible distributions of balls having an even number of balls in each box.

Answer 2

I remember solving a similar problem on a combinatorics test by forming a bijection to the problem of finding the shortest path on an NxM grid. This is a well known problem, basically imagine you have a grid of width N and height M. Now, starting from the bottom left, how many paths are there that only ever move either up or right (that is, they never backtrack, and thus are all "shortest paths"). The answer is (N + M) choose N.

Now we simply have to form said bijection by expressing the problem in terms of this grid. Imagine the Width of the grid represents each box, and the height how many balls are in said box. Now, since each box needs an even number, then each "step up" in the grid represents two balls. So for example, this path:

Represents the arrangment: 10 balls in the first box, 2 in the second box, 2 in the third box, and 6 in the fourth. Again, this is because our path starts by moving up 5 rows (and each step up represents 2 balls), then moves up 2 more rows (2 * 2 = 4), 2 again, then 3 additional rows. As you can see, every path we generate necessarily has to represent an arrangment of 20 balls. The trivial path:

Represents the case of 0 balls in the first 3 boxes and 20 balls in the last. As I said earlier, to find the total number of paths we just do (N + M) choose N, which happens to be (10 + 3) choose 10 = 268.