Distribution of $r$ objects into $4$ boxes.

balls-in-binscombinatorics

The number of ways of distributing $r$ distinct objects into $4$ distinct boxes such that box $1$ and $2$ must each hold an even number of objects and box 3 must hold an odd number of objects.

Each object has 4 different options/ boxes to go in, so the total number of ways are $4^r$.
I am not able to further make progress with the conditions to the problem.

The solution links this problem to the exponential function but I'm not able to understand it.

Best Answer

This is the sort of thing that generating functions are good at.

The generating function for the number of ways to distribute the $r$ objects over the $4$ boxes without constraints, with $a$ through $d$ marking the number of objects in each box, is $(a+b+c+d)^r$, and we get the total number of arrangements, summed over all possible distributions over the boxes, by substituting $a=b=c=d=1$, which yields $4^r$.

If we had a single constraint that the first box must contain an even number of objects, the generating function would be $\frac12\left((a+b+c+d)^r+(-a+b+c+d)^r\right)$ (which includes only the even powers of $a$), so the number of arrangements, obtained by substituting $a=b=c=d=1$, would be $\frac12\left(4^r+2^r\right)$.

Likewise, if we had a single constraint that the third box must contain an odd number of objects, the generating function would be $\frac12\left((a+b+c+d)^r-(a+b-c+d)^r\right)$ (which includes only the odd powers of $c$), so the number of arrangements, obtained by substituting $a=b=c=d=1$, would be $\frac12\left(4^r-2^r\right)$.

As it is, we have three simultaneous constraints, and we have to apply them one after the other to get the corresponding generating function that contains only the even powers of $a$ and $b$ and the odd powers of $c$:

\begin{eqnarray} f_0(a,b,c,d) &=&(a+b+c+d)^r\;,\\ f_1(a,b,c,d) &=& \frac12(f_0(a,b,c,d)+f_0(-a+b+c+d)) \\ &=& \frac12\left((a+b+c+d)^r+(-a+b+c+d)^r\right)\;, \\ f_2(a,b,c,d) &=&\frac12(f_1(a,b,c,d)+f_1(a,-b,c,d)) \\ &=&\frac14\left((a+b+c+d)^r+(-a+b+c+d)^r+(a-b+c+d)^r+(-a-b+c+d)^r\right)\;, \\ f_3(a,b,c,d) &=&\frac12(f_2(a,b,c,d)-f_2(a,b,-c,d)) \\ &=&\frac18\left((a+b+c+d)^r+(-a+b+c+d)^r+(a-b+c+d)^r+(-a-b+c+d)^r\right.\\ &&\left.-\left((a+b-c+d)^r+(-a+b-c+d)^r+(a-b-c+d)^r+(-a-b-c+d)^r\right)\right)\;. \end{eqnarray}

Again, the total number is obtained by substituting $a=b=c=d=1$, which yields

$$ \frac18\left(4^r+2^r-(-2)^r\right)\;. $$

The first few values for $r=1,2,3$ are $1,2,10$, which you can check by hand.

(Note that the result doesn’t hold for $r=0$, since in this case e.g. $(a+b-c-d)^r$ can’t be treated as $0$; we actually get a $1$ from each of the eight terms, and they cancel, yielding the correct count of $0$.)

Edit:

This is a too-long-for-a-comment response to @Semiclassical’s observation that the result is exactly $\frac18$ of the unconstrained result if $r$ is even.

If $r$ is even, the fourth box must also contain an odd number of objects, so the count is the same as if we had two even and two odd constraints.

On the level of the generating functions, no $2^r$ term results in this case because the terms obtained by exchanging the even and odd constraints have opposite signs and cancel.

But there’s also a direct combinatorial argument. If we distribute an even number of balls, there are $8$ possible resulting parity patterns for the boxes – all even, all odd, or $\binom42=6$ arrangements of two even, two odd. If we distribute $r-1$ objects without constraints, there’s exactly one box in which we can put the $r$-th object in order to make all boxes have the same parity. Thus, of the $8$ possible parity patterns, all even and all odd together have $\frac14=\frac28$ of the sequences, exactly their fair share. Since there’s permutation symmetry among the remaining $6$ parity patterns, they must each also have their fair share, $\frac184^r$.