a)
We will define, create and interpret generating functions.
Generating Functions
An infinite sequence can be associated with an infinite series A finite sequence can associated with a polynomial in a similar manner. This infinite series (or polynomial) is called the generating function of the sequence.
Given a sequence , the function is
called the generating function of the sequence. If the sequence is finite: , the 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
.
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 are not interested in the interval of convergence of these series, but just the relationship between the series and the corresponding sequence of coefficients.
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 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) Find a compact form for the generating function whose coefficients give
the number of non-negative integer solutions to the following equation in variables:
(problem 5b) Find a compact form for the generating function whose coefficients give
the number of non-negative integer solutions to the following equation in variables:
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 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.