# Generating functions - Stocking stores

I'm doing a bit of exam revision and came across the following question. I would like to know if my working (thus answer) is correct, or where I've gone wrong.

Four stores are getting new lawnmowers in. Each outlet must get at least 5 lawn-mowers. The two small outlets can cope with at most 20 lawnmowers, while the larger two can cope with at most 29. A shipment containing 60 lawn mowers has arrived. How many ways can they be distributed?

My working goes as follows:

Give each store 5 of the mowers to satisfy the first condition. There are now 40 mowers to distribute, resulting in the generating function

$$f(x) = \left(1 + x + x^2 + \cdots + x^{15}\right)^2\left(1 + x + \cdots + x^{24}\right)^2$$

Then solve for the coefficient of $x^{40}$

$$f(x) = \left(1 - x^{16}\right)^2\left(1 - x^{25}\right)^2\left(1 - x\right)^{-4}$$

Expanding this function gives:

$$\left({2 \choose 0} - {2 \choose 1}x^{16} + {2 \choose 2}x^{32}\right)\left({2 \choose 0} - {2 \choose 1}x^{25} + {2 \choose 2}x^{50}\right)\left(\sum\limits_{i=0}^n {-4 \choose i}x^i\right)$$

Then multiplying the factors to get $x^{40}$ terms gives:

$${43 \choose 40} - {2 \choose 1}{27 \choose 24} -{2 \choose 1}{18 \choose 15} + {2 \choose 2}{11 \choose 8} = 5024$$

Is this correct, if not could you let me know where I went wrong.

Thanks

-
I didn’t check the generating function computations in detail, but $$\binom{43}{40}-2\binom{27}{24}-2\binom{18}{15}+\binom{11}8$$ is exactly what I get by a straightforward stars-and-bars and inclusion-exclusion argument. – Brian M. Scott Jun 3 '12 at 10:34
The g.f. computations look good to me. – Gerry Myerson Jun 3 '12 at 10:38
Thanks, looks like I'm starting to get the hand of generating functions. – urbanyoung Jun 3 '12 at 10:41

## 1 Answer

What you have done is correct for 4 distinguishable stores and 60 indistinguishable lawnmowers.

You could have been slightly more direct with $$f(x) = \left(x^5 + x^6 + x^7 + \cdots + x^{20}\right)^2\left(x^5 + x^6 + \cdots + x^{29}\right)^2$$ and solved for the coefficient of $x^{60}$ in $$f(x) = x^{20} \left(1 - x^{16}\right)^2\left(1 - x^{25}\right)^2\left(1 - x\right)^{-4}$$ getting the same result.

-