Combinatorics - Generating Functions

In summary, the conversation discusses a problem where John needs to spend his remaining time 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. This is equivalent to finding non-negative integral solutions to a specific equation, which can be represented by a generating function. The correct generating function is given as g(x) = (1-x^3)/(1-x)(1-x^8)/(1-x^2)(1-x^2)/(1-x)(x/(1-x)).
  • #1
mattmns
1,128
6
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.
 
Physics news on Phys.org
  • #2
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
Thanks. I wondered about that for [itex]e_2[/itex]

So it should then be:

[tex]\frac{1-x^8}{1-x^2}[/tex]
 
  • #4
Yes, that's what it should be.
 

1. What is a generating function in combinatorics?

A generating function in combinatorics is a mathematical tool used to count the number of possible combinations or arrangements of a given set of objects. It is represented as a power series or polynomial where the coefficients correspond to the number of ways a particular combination or arrangement can occur.

2. How is a generating function different from a regular function?

A generating function is different from a regular function in that it is used to represent a sequence of numbers rather than a single value. It provides a compact and efficient way to represent and manipulate large numbers of terms, making it a useful tool in combinatorics.

3. What are the advantages of using generating functions in combinatorics?

Generating functions have several advantages in combinatorics, including the ability to easily manipulate large numbers of terms, the ability to handle complex counting problems, and the ability to use algebraic techniques to solve problems that would otherwise be difficult to solve.

4. Can generating functions be used to solve real-world problems?

Yes, generating functions have many real-world applications, including in fields such as computer science, physics, and statistics. They can be used to solve problems involving combinations, permutations, and other counting problems, making them a valuable tool in many areas of science and mathematics.

5. Is there a limit to the types of problems that can be solved using generating functions?

No, generating functions are a versatile and powerful tool that can be used to solve a wide range of problems in combinatorics and other fields. However, they may not always be the most efficient or practical solution, and other techniques may be more suitable depending on the problem at hand.

Similar threads

  • Calculus and Beyond Homework Help
Replies
14
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
815
  • Calculus and Beyond Homework Help
Replies
14
Views
498
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
967
Replies
4
Views
996
  • Cosmology
Replies
6
Views
485
Replies
1
Views
603
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Back
Top