1. Not finding help here? Sign up for a free 30min 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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Combinatorics - Generating Functions
  1. Combinatorics problems (Replies: 8)

  2. Combinatorics Question (Replies: 4)

  3. Combinatorics question (Replies: 2)