Number of ways to distribute balls into boxes

Question

We are given $N$ boxes and $M$ balls. We are required to find he number of ways of distributing the balls into the boxes such that each box has even number of balls.

We consider each ball to be distinct. Similarly, each box is distinct.

For examples : if $N = 2$, $M = 4$, then the answer is $8$. The possible ways are :

{{}, {1, 2, 3, 4}}

{{1, 2}, {3, 4}}

{{1, 3}, {2, 4}}

{{1, 4}, {2, 3}}

{{2, 3}, {1, 4}}

{{2, 4}, {1, 3}}

{{3, 4}, {1, 2}}

{{1, 2, 3, 4}, {}}

Please help me find some closed formula for it.

Answer 1

If you have $m$ equal balls and thus $m/2$ equal pairs of balls and $n$ different boxes.

Hence you have to put all the pairs in line, and make $n-1$ splits from 1 to $m/2$.

The $i$ split goes into the $i+1$ box. The nonsplitted first set goes to the 1st box.

If a ball is chosen twice, the corresponding box for that split is empty: you are selecting no box for that split.

Hence the arrangement leads to: $$ {m \choose n-1} $$ combinations.

I dont believe there is a closed solution for different balls (yet!).

Answer 2

If there are 2 boxes, a closed form is $2^{M-1}$.

Proof. Take $M-1$ of the balls and put them into boxes, 2 choices per ball. The position of the last ball is now fixed.

To extend this to more boxes, set $N-1$ balls aside.

At most $N-1$ of the boxes has the wrong parity of balls, hence, there is at least 1 way to put the last $N-1$ balls.

Hence, at least $N^{M-N+1}$ ways to arrange the balls in boxes.

A bit more thought reveals that for the $k$th last ball, it can be placed in at least $k$ different boxes. Hence instead of 1 way to arrange the last $N-1$ balls, we have $(N-1)!$ ways.

Hence at least $N!\times N^{M-N}$ ways.

If $N$ is fixed, we can compute a closed form for that particular $N$ with this observation.

Let $a_{k,l}$ be the number of ways to put $k$ balls in $N$ boxes such that $l$ boxes have an odd number of balls.

Then (ignoring edge cases) $a_{k+1,l}=a_{k,l-1}\times(N-l+1)+a_{k,l+1}\times(l+1)$, which is a linear combination.

Using this, we can write this information into a matrix. Let $a_k$ be the vector (of $N+1$ entries), the $i$th entry being $a_{k,i}$. Hence, we have:

$a_k=A^ka_0$ for some matrix $A$.

$a_0$ is a vector with $a_{0,0}=1$, $a_{0,i}=0$ for nonzero $i$. You can try diagonalising the matrix to solve for $a_{k,0}$ as a function in $k$.