Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.


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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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


share|cite|improve this answer
Trying to generalize the solution: Get the generating function to one of the familiar forms and use it to find the coefficient. True? – MichaelS Oct 21 '11 at 17:32
I don't want to exclude 0 as a multiple of 4, it was a mistake. I edited the question to fix it. – MichaelS Oct 21 '11 at 18:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.