Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

2 Answers

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|improve this answer
1  
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
add comment

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

share|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
add comment

Your Answer

 
discard

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.