6
$\begingroup$

Problem

How many ways dividing $n$ balls into $3$ buckets with the following limitations(?):

  • 1st bucket contains odd number of balls.
  • 2nd bucket contains a multiplication of 4 number of balls.
  • 3rd bucket contains either 0 or 2 balls exactly.

I'm trying to solve this problem using Generating Functions.

Solution

Lets find the generating functions using the above limitaions: $(x+x^3+...)(1+x^4+x^8+...)(1+x^2) = x(1+x^2 +...)(1+x^4 + ...)(1+x^2)$ $= x (1+x^2) \frac{1}{1-x^2} \frac{1}{1-x^4}$

Now is the point I get stuck. What should I do next? Should I find the coefficient of $x^n$? If so, how?

  • 0
    @joriki: Using your suggestion I don't even need to use generating functions, am I? (I've edited the question to count$0$as multiple of 4)2011-10-21

2 Answers 2

2

Eliminating the common factor $(1+x^2)$ from the numerator and denominator, you have $ x\left(1-x^2\right)^{-2} = x \cdot \sum_{k=0}^{\infty}{(k+1) x^{2k}} = \sum_{k=0}^{\infty}{(k+1)x^{2k+1}} = \sum_{\text{odd } k}\frac{k+1}{2}x^k. $ So, looking at the coefficient of $x^n$, there are $\frac{n+1}{2}$ ways to legally divide the balls if $n$ is odd, and none if $n$ is even.

  • 0
    It's a change in the summation variable. Define $k'=2k+1$. Then $k+1=(k'+1)/2$, and when $k=0,1,2,...$, the new variable $k'=1,3,5,...$. Then rename $k'\rightarrow k$.2011-10-24
0

If you want to exclude 0 as a multiple of 4 (which just gives the factor of $x^4$) you can finish your calculation by using $1-x^4=(1-x^2)(1+x^2)$ and then finding the coefficients of $\frac 1 {(1-x^2)^2}$ by using

$(1-x)^{-2}=\sum_{n=0}^{\infty}(n+1)x^n.$

  • 0
    I don't want to exclude 0 as a multiple of 4, it was a mistake. I edited the question to fix it.2011-10-21