0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Do you know the answer if the even stipulation wasn't there ? $\endgroup$ Dec 8, 2020 at 11:59
  • $\begingroup$ Also I assume you are considering no balls in a bin as even. Can you confirm? $\endgroup$
    – Math Lover
    Dec 8, 2020 at 12:43
  • $\begingroup$ 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. $\endgroup$
    – Tis Fake
    Dec 8, 2020 at 16:37

1 Answer 1

0
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ So, when we generate function why should we count until k terms instead of k/2 terms? $\endgroup$
    – Tis Fake
    Dec 10, 2020 at 6:42
  • $\begingroup$ 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? $\endgroup$
    – Tis Fake
    Dec 10, 2020 at 7:11
  • $\begingroup$ You mean infinite terms that you may see in answers .. $ \, (1 + x^2 + x^4 + ...\infty)$? $\endgroup$
    – Math Lover
    Dec 10, 2020 at 7:17
  • $\begingroup$ Yes. like d.umn.edu/~jgreene/Combinatorics/Fall_2015/… for example if you look at the first example. $\endgroup$
    – Tis Fake
    Dec 10, 2020 at 7:21
  • $\begingroup$ 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. $\endgroup$
    – Math Lover
    Dec 10, 2020 at 7:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .