How many ways to select $n$ balls using generating function

360 Views Asked by At

Given an infinite number of red, orange and yellow balls. In how many ways can you select $n$ balls if order doesn't matter and the number of red balls must be at least twice as big as the number of orange balls? This is what I tried so far:

If $x_1$ is the number of red balls, $x_2$ the number of orange balls and $x_3$ the number of yellow balls, then we know:

$$x_1 \geq 2x_2,$$

$$x_1 + x_2 + x_3 = n.$$

From $x_1 \geq 2x_2$ follows $x_1 - 2x_2 \geq 0$, and if we create a new variable $x_4 = x_1 -2x_2$ then we find $x_4 \geq 0$. Since $x_4 = x_1 -2x_2$ it follows that $x_1 = x_4 + 2x_2$. Now we find $x_1 + x_2 + x_3 = x_4 + 2x_2 + x_2 + x_3 = x_4 + 3x_2 + x_3 = n$ with $x_4 \geq 0$.

For the individual generating functions I found:

$$A_3(x) = A_4(x) = 1 + x + x^2 + ... = \frac{1}{1-x},$$

$$A_2(x) = 1 + x^3 + x^6 + .... = \frac{1}{1-x^3},$$

so for the total generating function I found:

$$A_x(x) = \frac{1}{(1-x)^2(1-x^3)}.$$

I want to rewrite this to the form $\sum_{n=0}^{\infty} ... x^n$, but I am not sure how to do that.

1

There are 1 best solutions below

0
On

$a$ is the number of orange balls
$2a+b$ is the number of red balls
$c$ is the number of yellow balls

We want $$ 3a+b+c=n\tag1 $$ The generating function is $$ \begin{align} \overbrace{\ \frac1{1-x^3}\ }^{3a}\overbrace{\ \ \frac1{1-x}\ \ }^{b}\overbrace{\ \ \frac1{1-x}\ \ }^{c} &=\overbrace{\sum_{k=0}^\infty\binom{-1}{k}\left(-x^3\right)^k}^{\frac1{1-x^3}}\overbrace{\sum_{j=0}^\infty\binom{-2}{j}(-x)^j}^{\left(\frac1{1-x}\right)^2}\\ &=\sum_{k=0}^\infty x^{3k}\sum_{j=0}^\infty(j+1)x^j\tag2 \end{align} $$ Using the Cauchy product formula, we get the coefficient for $x^n$ to be $$ \begin{align} \sum_{k=0}^{\left\lfloor\frac{n+1}3\right\rfloor}(n-3k+1) &=(n+1)\left\lfloor\frac{n+4}3\right\rfloor-\frac32\left\lfloor\frac{n+4}3\right\rfloor\left\lfloor\frac{n+1}3\right\rfloor\\ &=\left\lfloor\frac{n+4}3\right\rfloor\left(n+1-\frac32\left\lfloor\frac{n+1}3\right\rfloor\right)\\[6pt] &=\frac{(n+4)(n+1)}6+\frac32\left(\left\{\frac{n+1}3\right\}-\left\{\frac{n+1}3\right\}^2\right)\\ &=\bbox[5px,border:2px solid #C0A000]{\left\lfloor\frac{(n+2)(n+3)}6\right\rfloor}\tag3 \end{align} $$