# Generating function for distributing $k$ indistinguishable elements into $n$ distinguishable bins such that each bin has even number of elements.

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?

• Do you know the answer if the even stipulation wasn't there ? Dec 8, 2020 at 11:59
• Also I assume you are considering no balls in a bin as even. Can you confirm? Dec 8, 2020 at 12:43
• Yes @MathLover no balls in a bin is also even. Not really, the even stipulation is just a condition i guess, the result would be similar with or without the stipulation. Dec 8, 2020 at 16:37

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}$$.

• So, when we generate function why should we count until k terms instead of k/2 terms? Dec 10, 2020 at 6:42
• Majority of answers about boxes in balls problem are open ended i.e. {1+x^2 +x^4+..................) and are not limited by the number of balls, can you tell me why in this problem we limit it? Dec 10, 2020 at 7:11
• You mean infinite terms that you may see in answers .. $\, (1 + x^2 + x^4 + ...\infty)$? Dec 10, 2020 at 7:17
• Yes. like d.umn.edu/~jgreene/Combinatorics/Fall_2015/… for example if you look at the first example. Dec 10, 2020 at 7:21
• It is a choice. I prefer to do this way. Both work and lead to the same answer. If you are used to doing it that way, I can show how it would work here using infinite terms. Let me know if you want me to edit and show that. Dec 10, 2020 at 7:24