How many ways dividing $n$ balls into $3$ buckets with limitations?

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?

• You can simplify the problem considerably by noting that all remainders mod $2$ are fixed, so $n$ must be odd and you can put the odd ball in the first bucket and then distribute the rest of the balls in pairs -- the constraints then become 1. no constraint, 2. even number, 3. 0 or 1 balls. Also note that you didn't count $0$ as a multiple of $4$ in your generating function (which it is). – joriki Oct 21 '11 at 17:10
• @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) – MichaelS Oct 21 '11 at 17:19

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.
• can you please elaborate on how you done the last transition ?$$\sum_{k=0}^{\infty}{(k+1)x^{2k+1}} = \sum_{\text{odd } k}\frac{k+1}{2}x^k$$ – MichaelS Oct 21 '11 at 18:26
• 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$. – mjqxxxx Oct 24 '11 at 19:31
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.$$