There are two kinds of flowers in a shop. Roses cost 3 dollars each while carnations cost 2 dollars each. How many different kinds of bouquets can be bought with exactly 50 dollars?
My solution:
We can purchase $1,2,3,...$ roses, each cost $3$ dollars which gives the choices $(1+x^3+x^6+...)$. Likewise we can choose $(1+x^2+x^4+...)$ carnations. We define our generating function as:
$G(x) = (1+x^2+x^4+...)(1+x^3+x^6+...)=(-1/(x^3-1))(-1/(x^2-1))=(x^2-1)^{-1}(x^3-1)^{-1}$
We are to count the number of combinations where the total cost is 50 dollars, hence we're looking for $[x^{50}]$.
How can one compute $[x^{50}]G(x)?$
Use trusty partial fractions...
$\begin{align*} [x^{50}] \frac{1}{(1 - x^2) (1 - x^3)} &= [x^{50}] \left( \frac{1}{3 (1 + x + x^2)} + \frac{1}{4 (1 + x)} + \frac{1}{4 (1 - x)} + \frac{1}{6 (1 - x)^2} \right) \\ &= [x^{50}] \frac{1 - x}{3 (1 - x^3)} + \frac{1}{4} \cdot (-1)^{50} + \frac{1}{4} + \frac{1}{6} \cdot \binom{-2}{50} \\ &= \frac{1}{3} \cdot [x^{50}] \frac{1}{1 - x^3} - \frac{1}{3} \cdot [x^{49}] \frac{1}{1 - x^3} + \frac{1}{2} + \frac{1}{6} \cdot \binom{50 + 2 - 1}{2 - 1} \\ &= 9 \end{align*}$
The powers of $x$ that appear in $(1 - x^3)^{-1}$ are all multiples of 3, and neither 50 nor 49 qualify.