# Thread: generating functions again! :(

1. ## generating functions again! :(

Heather just had new neighbours move in next door and would like to make a fruit basket for
them. When her husband returned from the grocery store he had a bag containing apples,
bananas, and oranges. How many different possibilities are there for a fruit basket consisting
of exactly 36 pieces of fruit if
(a) there is an ample supply of apples and bananas, but there are only 4 oranges?
(b) there are 16 of each kind of fruit?
(c) there is an ample supply of bananas and oranges, and there are 4 distinguishable apples
(one Fuji, one Macintosh, one Spartan, and one Ambrosia)?

(In each case, fruit baskets are distinguished
solely by how many of each type of fruit they contain.)

2. Originally Posted by sbankica
Heather just had new neighbours move in next door and would like to make a fruit basket for
them. When her husband returned from the grocery store he had a bag containing apples,
bananas, and oranges. How many different possibilities are there for a fruit basket consisting
of exactly 36 pieces of fruit if
(a) there is an ample supply of apples and bananas, but there are only 4 oranges?
(b) there are 16 of each kind of fruit?
(c) there is an ample supply of bananas and oranges, and there are 4 distinguishable apples
(one Fuji, one Macintosh, one Spartan, and one Ambrosia)?

(In each case, fruit baskets are distinguished
solely by how many of each type of fruit they contain.)
I'll get you started on (a).

Let $\displaystyle a_r$ be the number of ways to prepare a fruit basket with r pieces of fruit. We want to find the Ordinary Power Series Generating Function (OPSGF) $\displaystyle f(x) = \sum_r a_r x^r$.

The OPSGF for the number of apples is
$\displaystyle 1 + x + x^2 + \dots = (1-x)^{-1}$,

the series for the number of bananas is the same,
and the series for the number of oranges is
$\displaystyle 1 + x^2 + x^3 + x^4 = 1 + x^2 + x^3 + \dots - (x^5 + x^6 + x^7 + \dots) = (1-x)^{-1} - x^5 \; (1-x)^{-1}$

So
$\displaystyle f(x) = (1-x)^{-1} \cdot (1-x)^{-1} \cdot [ (1-x)^{-1} - x^5 \; (1-x)^{-1} ]$
$\displaystyle = (1 - x^5) \; (1-x)^{-3}$

The number of ways to get 36 pieces of fruit in the basket is the coefficient of $\displaystyle x^{36}$ when f is expanded as a series.

Do you see how to find this coefficient?