a)
We will define, create and interpret generating functions.
1 Generating Functions
An infinite sequence, , can be associated with an infinite series This infinite series is called the generating function of the sequence. A finite sequence can be associated with a polynomial similarly.
Given a sequence , the function is called the generating function of the sequence.
If the sequence is finite: , then its generating function is the polynomial
In this section, we prefer to start our sequence with the term denoted rather than so
as to align the subscript in the generating function with the power of . In particular,
the tern is added to the Fibonacci sequence.
Before presenting examples of generating functions, it is important for us to recall two specific examples of power series. The first is the geometric power series and the second is the Maclaurin series for the exponential function In the context of generating functions, we focus on the relationship between the series and its sequence of coefficients rather than on the interval of convergence.
example 1 Find the generating function for the sequence and write it in a compact
form.
The generating function for this sequence is This is a geometric series with common ratio , so it can be written more compactly as
The generating function for this sequence is This is a geometric series with common ratio , so it can be written more compactly as
example 2 Find the generating function for the sequence and write it in a compact
form.
Recognizing the numbers in the sequence as , we have This is the exponential function with in the place of (since ) and hence the generating function can be written more compactly as
Recognizing the numbers in the sequence as , we have This is the exponential function with in the place of (since ) and hence the generating function can be written more compactly as
The next example investigates the relationship between generating functions and solutions to combinatorial problems.
example 3 Flip a coin and consider the function . The coefficient of represents the
number ways of obtaining “heads”. Now flip the coin twice and consider the function
. Note that there is one way to get zero heads: TT. There are two ways to get one
heads, HT and TH, and there is one way to get two heads, HH. Thus, the function
encodes then number of ways to get heads in two flips of the coin, where
.
(problem 3a) Based on the example above guess the generating function
corresponding to counting the number of heads in 3 coin flips. Express your guess
both as a power of as a proper generating function with numerical coefficients. Verify
that your guess is correct.
(problem 3b) Generalize your answer to the last problem by creating the
generating function corresponding to the number of heads in coin flips.
Express your answer as a power of and verify your answer using the Binomial
Theorem.
example 4 Consider a six-sided die whose faces are numbered 1 through 6. If it is
rolled once, the function encodes the number of ways of obtaining the outcome
corresponding to the degree of a particular term. Now roll the die twice and consider
the sum. It can be . Squaring gives The coefficient of in gives the number of ways
of rolling a sum of (verify).
(problem 4) Consider a six-sided die whose faces are numbered 1 through 6. Roll the
die 3 times and consider the sum. What are the minimum and maximum possible
values of the sum? Create a generating function whose coefficients encode the
number of ways of rolling a sum of . Express your answer as a power of
from the example above. Find the coefficient of . Verify that this coefficient
is indeed the number of ways of obtaining a sum of by enumerating the
possibilities.
example 5 Consider the number of non-negative integer solutions of the following
equation in variables: Find the generating function whose coefficients give the
number of such solutions.
Each variable can take on any value (up to the maximum possible , which is unspecified) and so it will contribute a factor of Hence
Each variable can take on any value (up to the maximum possible , which is unspecified) and so it will contribute a factor of Hence
(problem 5a) Use the geometric series approach to find a compact expression for the
generating function whose coefficients count the number of non-negative integer
solutions to the equation:
For each value of , this is the number of ways to put identical objects into bins.
(problem 5b) Use a geometric series approach to find a compact form for
the generating function whose coefficients give the number of non-negative
integer solutions to the equation (in variables): For each value of , the
number of solutions is the number of ways to put identical objects into
bins.
example 6 Consider the number of non-negative integer solutions of the equation if
the variables are subject to the following conditions: Each variable will contribute a
factor according the condition it must satisfy. The variable will contribute the factor
The variable will contribute the factor The variable will contribute the factor and
the variable will contribute the factor The generating function is the product of
these factors: The coefficient of in the Maclaurin series expansion of this function
gives the number of solutions to the given equation whose variables satisfy the given
conditions.
(problem 6) Consider the number of non-negative integer solutions of the equation if
the variables are subject to the following conditions:
2025-04-05 17:18:44