# Generating function on number of ways to purchase a bouquet with exactly 50 dollars

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)?$$

• Binomial series? – saulspatz Aug 1 at 17:19
• @saulspatz well, kind of unsure since it is the product of two binoms :s – Hassebae Aug 1 at 17:53
• Well, I don't know if it simplifies much, because I haven't written it out, but in one factor, the degrees are all even, and in the other they're multiples of $3$, so there aren't many ways to make $50$. – saulspatz Aug 1 at 18:35

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