1

How many ways are there to divide 100 balls into two cells, such that in the first cell there must be at least $2$ balls, while in the other cell there must be even number of balls.

I want to solve it using generating functions.
First, We'll present each demand as a polynomial:

$$({x^2} + {x^3} + {x^4} + ...)({x^0} + {x^2} + {x^4} + ...)$$

Now lets present those terms as a power series (I skipped a step here):

$$\frac{{{x^2}}}{{{{(1 - x)}^2}(1 + x)}}$$

Using this "fractions method" (I can't recall it's formal name):

$$\frac{{{x^2}}}{{{{(1 - x)}^2}(1 + x)}} = \frac{A}{{{{(1 - x)}^2}}} + \frac{B}{{(1 + x)}}$$

We have that $A={1\over 2}$ and $B={1\over 4}$.

We recall that dividing by $(1-x)$ produces the "partial sums series". Hence,

$${F_1} = \frac{1}{{2{{(1 - x)}^2}}} = \frac{1}{2}\left\{ {1,2,3,4...} \right\}$$

$${F_2} = \frac{1}{{4(1 + x)}} = \frac{1}{{4(1 - ( - x))}} = \frac{1}{4}\left\{ { - 1,1, - 1,1...} \right\}$$

Am I right so far?
How to extract the number of possibilities from those two generating functions? (I am new with that, sorry if it's a newbie question).

AndrePoole
  • 3,271

1 Answers1

1

I think something goes wrong with your $A$ and $B$. I think you should want to use the "fraction method" like
$$ \frac{1}{(1-x)^2(1+x)}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{1+x} $$ And find $A,B,C$ that help.

But when you have $f_1f_2=(x^2+x^3+x^4+...)(x^0+x^2+x^4+...)$. You want the coefficient of the term $x^{100}$. For every $x^k$ in $f_1$ there is exactly one terms to make the exponent $100$ if $2\leq k\leq 100 $ and $k$ even.There are $50$ such $k$'s so $50$ possibilities.

But maybe it is nice to notice that $$\frac{1}{(1-x)^2}=\frac{d}{dx}\left( \frac{1}{1-x}\right)$$ So you can say $\frac{1}{(1-x)^2}=1+2x+3x^2+...$

Then you want to know the coefficient in front op $x^{98}$ of $(1+2x+3x^2+...)(1-x+x^2-x^3+....)$ that equals $\sum_{i=0}^{49}((2k+1)-2k)=50$

Kaladin
  • 1,485