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]
    where,
    [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

    0rthodontist

    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:

    [tex]\frac{1-x^8}{1-x^2}[/tex]
     
  5. Nov 20, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

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