Distributing 21 balls in 3 urns with some condition

Question

In how many ways can we distribute $21$ distinct balls in $3$ different urns such that the first urn contains an even and the second urn contains an odd number of balls? Since $21$ can be written only as the sum of three odd numbers or two even numbers and an odd number, we can say the number of distributions of $21$ balls in $3$ urns is: $$A_{1} + A_2{} + A_{3} + B$$ where: $$A_{i} = \text{The number of distributions where the ith urn contains an odd} \\ {\text{and the other urns contain an even number of balls}}$$ and: $$B = \text{The number of distributions where all urns contain an odd number of balls}$$ Now $A_{1} = A_{2} = A_{3}$ (say $x$) since any state of any of these three can be mapped to the other ones by changing the order of the urns. Now Looks like $B = x - 1$ and I want to prove this by defining a bijective function from the set of all states of the part $A_{1}$ excluding one particular element to the set of all the states of the part $B$ but the functions I define don't happen to be injective. (Moving one ball from an urn containing an even number of balls to the other one containing an even number of balls could be a possible solution but this function is not injective.) What function do you suggest for this? If we define a bijective function successfully then we'll have: $$x + x + x + x - 1 = 3^{21} \Rightarrow 4x - 1 = 3^{21} \Rightarrow x = \frac{3^{21} + 1}{4}$$ Which is the answer to the problem.

Answer 1

For odd number of balls in bin $1$, we are left with even number of balls to distribute between bin $2$ and $3$.

If the number of even balls is $2k \ (k \in \mathbb{Z+})$, then keeping one of the balls aside, there are $ \ 2^{(2k-1)} \ $ possible ways to distribute balls in two bins. Every arrangement will have even number of balls in one of the bins and odd in the other. But by fixing the position of the last ball as the bin with odd number of balls, $2^{(2k-1)}$ is the number of arrangements of $2k$ balls in two bins such that both bins have even number of balls. As there are $2^{2k}$ arrangements in total, that leaves us with same number of arrangements $2^{(2k-1)}$, where there are odd number of balls in both bins.

The above holds true for any odd number of balls but when there are $21$ balls in bin $1$, $k = 0$ and total number of arrangements in bin $2$ and $3$ is $2^{2k} = 1$, which is odd - there is one arrangement $\{21 \ \ 0 \ \ 0\}$ with even number of balls in bin $2$ and $3$ but there are no arrangements with odd number of balls in bin $2$ and $3$.

That leads to $ \ 3 x + (x-1) = 3^{21}$.

Answer 2

I know this doesn't particularly answer your question, but I found a beautiful generating functions solution to the problem that I would like to share.

The number of total distributions will be the coefficient of $x^{21}$ in the generating function $$21!\left(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\right)\left(\sum_{k=0}^\infty \frac{x^{2k+1}}{(2k+1)!}\right)\left(\sum_{k=0}^\infty \frac{x^{k}}{k!}\right)$$

To explain why this is true, consider that each series term represents each urn.

When we expand this product and collect all the terms with coefficient $x^{21}$, we are summing over all nonnegative integer solutions to $(2a)+(2b+1)+c=21$.

For each of these particular ordered partitions of $21$, we are summing the coefficient $\binom{21}{2a,2b+1,c}$, which represents the total number of ways to distribute the $21$ distinct balls so that $2a$ balls are in the first urn, $2b+1$ balls are in the second urn, and $c$ balls are in the third urn.

Now we must actually determine the coefficient of $x^{21}$ in our generating function. We can use the taylor series $$e^x=\sum_{k=0}^\infty \frac{x^k}{k!}$$ to simplify the sums.

Using roots of unity filter, we can also determine that $$\frac{e^x+e^{-x}}{2}=\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}$$ $$\frac{e^x-e^{-x}}{2}=\sum_{k=0}^\infty \frac{x^{2k+1}}{(2k+1)!}$$ You can expand the taylor series of the LHS of these two identities to see that they are indeed true.

Using these identities, our generating function simplifies to $$21!\left(\frac{e^x+e^{-x}}{2}\right)\left(\frac{e^x-e^{-x}}{2}\right)\left(e^x\right)$$ $$21!\left(\frac{e^{2x}-e^{-2x}}{4}\right)\left(e^x\right)$$ $$\frac{21!}{4}\left(e^{3x}-e^{-x}\right)$$ The coefficient of $x^{21}$ in the expansion of this expression is $$\frac{21!}{4}\left(\frac{3^{21}}{21!}-\frac{(-1)^{21}}{21!}\right)$$ $$\frac{3^{21}-(-1)^{21}}{4}$$ $$\boxed{\frac{3^{21}+1}{4}}$$