1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics - Generating Functions

  1. Nov 18, 2006 #1
    Here is the question from the book:
    John was recently diagnosed with a lethal disease and is said to have n hours left to live. John would like to spend his remaining time with his three girlfriends and wife, Jane, Jill, Joan and Amy, respectively. Assuming that John must spend between 0 and 2 hours with Jane, 0,2,4, or 6 hours with Jill, an even number of hours with Joan (including 0) and at least 1 hour with his wife Amy, determine the generating function [itex]h_{n}[/itex] of ways he can spend his remaining hours.


    So this problem is basically the same as the number of non-negative integral solutions to the following equation:

    [itex]e_1 + e_2 + e_3 + e_4 = n[/itex]
    [itex]0 \leq e_1 \leq 2, e_2 \in \{0,2,4,6\}, e_3 \in \{0,2,4,6,8,...\}, e_4 \in \{1,2,3,4,5,...\}[/itex]

    So we can associate with each [itex]e_i[/itex] the following series.

    [tex](e_1): 1 + x + x^2 = \frac{1-x^3}{1-x}[/tex]
    [tex](e_2): 1 + x^2 + x^4 + x^6 = \frac{1-x^7}{1-x^2}[/tex]
    [tex](e_3): 1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}[/tex]
    [tex](e_4): x + x^2 + x^3 + x^4 + ... = \frac{x}{1-x}[/tex]

    so, our generating function,

    [tex]g(x) = \frac{1-x^3}{1-x}\frac{1-x^7}{1-x^2}\frac{1}{1-x^2}\frac{x}{1-x}[/tex]

    Everything look good? Thanks.
  2. jcsd
  3. Nov 19, 2006 #2


    User Avatar
    Science Advisor

    It looks good except for your generating function for e2. Think of it as a series in y = x^2. What would that series in y be?
  4. Nov 19, 2006 #3
    Thanks. I wondered about that for [itex]e_2[/itex]

    So it should then be:

  5. Nov 20, 2006 #4


    User Avatar
    Science Advisor

    Yes, that's what it should be.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook