Generating functions

**sbankica** · November 13th 2009, 12:33 PM

A jar of 50 quarters and 20 loonies is to be divided amongst Alex, Kim, and Julie. How many
ways can this be done if Alex gets no quarters, Kim gets no loonies but at least 10 quarters,
and Julie gets an odd number of loonies? (Use generating functions to solve the problem)

**awkward** · November 14th 2009, 09:23 AM

Originally Posted by sbankica

A jar of 50 quarters and 20 loonies is to be divided amongst Alex, Kim, and Julie. How many
ways can this be done if Alex gets no quarters, Kim gets no loonies but at least 10 quarters,
and Julie gets an odd number of loonies? (Use generating functions to solve the problem)

Let's say the number of ways to get m quarters and n loonies is $a_{mn}$ . We want to find the 2-variable ordinary power series generating function (OPSGF) $f(x,y)=\sum_m \sum_n a_{mn} x^m y^n$ .

The OPSGF for Alex's coins is
$A = 1 + y + y^2 + \dots = (1-y)^{-1}$

For Kim's coins,
$K = x^{10} + x^{11} + x^{12} + \dots = x^{10} \; (1-x)^{-1}$

For Julie's coins,
$J = (1 + x + x^2 + \dots) \; (y + y^3 + y^5 + \dots) = (1-x)^{-1} \; y \; (1-y^2)^{-1}$

So
$f(x,y) = A \cdot K \cdot J = x^{10} \; y \; (1-x)^{-2} \; (1-y)^{-1} \; (1-y^2)^{-1}$

In a sense we are done, but maybe we should go ahead and find the answer to the original problem, which is the coefficient of $x^{50} y^{20}$ in f. We can factor f as
$f(x,y) = g(x) \; h(y)$ , where
$g(x) = x^{10} \; (1-x)^{-2}$ and
$h(y) = y \; (1-y)^{-1} \; (1-y^2)^{-1}$ .

$g(x) = x^{10} \; \sum_i (-1)^i \binom{-2}{i} x^i$
so $g[x^{50}] = (-1)^{40} \binom{-2}{40} = \binom{2+40-1}{40} = \binom{41}{40} = 41$

Next we need to find $h[y^{20}]$ , but it will simplify things if we first apply partial fractions to h:
$h(y) = y \cdot [(1/2) (1-y)^{-2} + (1/4) (1-y)^{-1} + (1/4) (1+y)^{-1}]$
$= y \cdot \left( (1/2) \sum_i (-1)^i \binom{-2}{i} y^i + (1/4) \sum_i y^i + (1/4) \sum_i (-1)^i y^i \right)$
so
$h[y^{20}] = (1/2) (-1)^{19} \binom{-2}{19} + (1/4) + (1/4) (-1)^{19}$
$= (1/2) \binom{2+19-1}{19} = (1/2) \binom{20}{19} = 10$

So the number of ways to get 50 quarters and 20 loonies is
$g[x^{50}] \cdot h[y^{20}] = 41 \cdot 10$

Thread: Generating functions

LinkBack

Thread Tools

Display

Generating functions

Similar Math Help Forum Discussions

Generating functions

generating functions

generating functions

Generating Functions

Generating functions...need some help here

Search Tags