1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Binomial series? $\endgroup$ – saulspatz Aug 1 at 17:19
  • $\begingroup$ @saulspatz well, kind of unsure since it is the product of two binoms :s $\endgroup$ – Hassebae Aug 1 at 17:53
  • $\begingroup$ 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$. $\endgroup$ – saulspatz Aug 1 at 18:35
3
$\begingroup$

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.

$\endgroup$

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.