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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – joriki Oct 21 '11 at 17:10
  • $\begingroup$ @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) $\endgroup$ – MichaelS Oct 21 '11 at 17:19
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$$ $\endgroup$ – MichaelS Oct 21 '11 at 18:26
  • $\begingroup$ 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$. $\endgroup$ – mjqxxxx Oct 24 '11 at 19:31
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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