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

Question

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?

Answer 1

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.

Answer 2

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