Generating function to find the number of ways to put marbles in a basket

Question

Write a generating function for the number of ways to make a basket of $n$ marbles, if you need to use at least one orange marble , an even number of yellow marbles, at most 2 green marbles, and any number of red marbles.

Because the question is asking for a generating function, it seems to me like it may be possible to create a recurrence relation and then solve the relation to create the generating function. However, I'm not sure how to go about finding that relation. The fact that we need an even number of yellow marbles is giving me trouble.

For instance, if we ignore that we need an even number of yellow marbles, we obtain:

(1) $n_o+n_y+n_g+n_r=n$ where $n_0>0$ and $n_g<3$ so what follows is

(2) $n'_o+n_y+n_g+n_r=n-1$ where $n_g<3$. Then we can solve the number of solutions to this equation minus the number of solutions where the number of green marbles is greater than or equal to 3 and take the difference between the two.

Where the number of solutions to (2)(ignoring the bounds on green marbles) is $n-1+4-1 \choose 3$=$n+2 \choose 3$

Any ideas on how to calculate the number of ways, say $f_n$, through a recurrence relation?

Answer 1

It’s easiest simply to write down the generating function. You want the coefficient of $x^n$ to be the number of ways to decompose $n$ as

$$n=n_o+n_y+n_g+n_r\;,\tag{1}$$

where $n_o\ge 1$, $n_g\le 2$, and $n_y$ is even. You can arrange this by noting that $n_o$ must be an exponent in the sum

$$x^1+x^2+x^3+\ldots\;,$$

$n_g$ must be an exponent in the sum

$$x^0+x^1+x^2\;,$$

$n_y$ must be an exponent in the sum

$$x^0+x^2+x^4+\ldots\;,$$

and $n_r$ must be an exponent in the sum

$$x^0+x^1+x^2+x^3+\ldots\;.$$

Thus, if you multiply these four expressions together, you’ll get one $x^n$ term for each solution to $(1)$ meeting the stated requirements. Your generating function is therefore

$$\left(\sum_{k\ge 1}x^k\right)(1+x+x^2)\left(\sum_{k\ge 0}x^{2k}\right)\left(\sum_{k\ge 0}x^k\right)\;.\tag{2}$$

It’s straightforward to convert each of the three infinite series in $(2)$ into the corresponding function, and all that then remains is to multiply them together along with the quadratic $1+x+x^2$.

Answer 2

Completing Brian Scott's answer, you are after the coefficient of $z^n$ in the following. This yields to partial fractions and using geometric series and (generalized) binomial theorem:

$\begin{align} [z^n] \left( \sum_{k \ge 1} z^k \right) \cdot &\left( 1 + z + z^2 \right) \cdot \left( \sum_{k \ge 0} z^{2 k} \right) \cdot \left( \sum_{k \ge 0} z^k \right) \\ &= [z^n] \frac{z}{1 - z} \cdot \left( 1 + z + z^2 \right) \cdot \frac{1}{1 - z^2} \cdot \frac{1}{1 - z} \\ &= [z^n] \frac{z (1 + z + z^2)}{(1 - z)^2 (1 - z^2)} \\ &= [z^n] \left( - \frac{1}{8} \frac{1}{1 + z} + \frac{7}{8} \frac{1}{1 - z} - \frac{9}{4} \frac{1}{(1 - z)^2} + \frac{3}{2} \frac{1}{(1 - z)^3} \right) \\ &= -\frac{1}{8} (-1)^n + \frac{7}{8} - \frac{9}{4} (-1)^n \binom{-2}{n} + \frac{3}{2} (-1)^n \binom{-3}{n} \\ &= - \frac{1}{8} (-1)^n + \frac{7}{8} - \frac{9}{4} \binom{n + 2 - 1}{2 - 1} + \frac{3}{2} \binom{n + 3 - 1}{3 - 1} \\ &= - \frac{1}{8} (-1)^n + \frac{7}{8} - \frac{9}{4} (n + 1) + \frac{3}{2} \frac{(n + 2) (n + 1)}{2} \\ &= \frac{18 n^2 + 3 - 3 \cdot (-1)^n}{24} \end{align}$

Tanks to maxima for the heavy lifting.