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?

  • 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).2011-10-21
  • 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.

  • 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$$2011-10-21
  • 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
    Trying to generalize the solution: Get the generating function to one of the [familiar forms](http://en.wikipedia.org/wiki/Generating_function#Ordinary_generating_functions) and use it to find the coefficient. True?2011-10-21
  • 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