# Homework Help: Combinatorics - Generating Functions

1. Nov 18, 2006

### mattmns

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 $h_{n}$ 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:

$e_1 + e_2 + e_3 + e_4 = n$
where,
$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,...\}$

So we can associate with each $e_i$ the following series.

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

so, our generating function,

$$g(x) = \frac{1-x^3}{1-x}\frac{1-x^7}{1-x^2}\frac{1}{1-x^2}\frac{x}{1-x}$$

Everything look good? Thanks.

2. Nov 19, 2006

### 0rthodontist

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?

3. Nov 19, 2006

### mattmns

Thanks. I wondered about that for $e_2$

So it should then be:

$$\frac{1-x^8}{1-x^2}$$

4. Nov 20, 2006

### 0rthodontist

Yes, that's what it should be.