Results 1 to 2 of 2

Math Help - Generating functions

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Exclamation Generating functions

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by sbankica View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2011, 05:30 AM
  2. generating functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 1st 2010, 02:15 AM
  3. generating functions
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 24th 2009, 08:01 AM
  4. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 05:43 PM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum