Generating function for distributing $k$ indistinguishable elements into $n$ distinguishable bins such that each bin has even number of elements.
So for the bins to have exactly even number of elements we assume that $k$ is even and we distribute them into pairs so there are $x = k/2$ indistinguishable elements to insert in $n$ bins. How do I generate the function for the series?
Best Answer
We have $k$ balls and $n$ bins where $k$ is even.
$\sum \limits_1^n b_i = k \,, \, b_i$ is number of balls in each bin and it is even.
If the restriction of even was not there, your polynomial for each factor (box) would be $(1 + x + x^2 + .. + x^k)$.
Given the restriction, we only pick even terms.
So the polynomial for each factor would be $(1 + x^2 + x^4 + .. + x^k) \,$ (considering empty box as even)
For $n$ factors, the generating function would be
$g(x) = (1 + x^2 + x^4 + .. + x^k)^n \,$. You have to take the coefficient of term $x^k$.
If you need to take this further,
$g(x) = (1+x^2+x^4+\dots +x^k)^n = \left( \frac{1-x^{k+2}}{1-x^2} \right)^n$
$ = (1-x^{k+2})^n \times (1-x^2)^{-n}$
$= \sum (-1)^i \binom{n}{i} x^{(k+2)i} \times \sum \binom{n + j - 1}{j} x^{2j}$
and take the coefficient of term $x^k$ which means
$(k+2)i + 2j = k \implies i = 0, j = \frac{k}{2} = m \, $ (say).
So we get ${n + m - 1 \choose m}$
Or you can simply use the infinite geometric series -
$g(x) = (1 + x^2 + x^4 + .. + ...)^n \, = \frac{1}{(1+x^2)^{n}} = (1+x^2)^{-n}$
$ = \sum \limits_{i=0}^{\infty} {n + i - 1 \choose i} x^{2i}$.
So $, \,i = \frac{k}{2} = m \,$ will be the $x^k$ term and coefficient is ${n + m - 1 \choose m}$.