Generating Functions
A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. Techniques such as partial fractions, polynomial multiplication, and derivatives can help solve the recurrence relations.
Contents
Ordinary Generating Functions
An ordinary generating function is one of the form which will be put to good use for the types of problems we are interested in.
How many ways are there to make a sum of using exactly one element from each of the following two sets: and
Consider the two polynomials and . Note that for the first polynomial, the coefficient of is the number of ways of making a sum of using one element from the first set, and similarly for the second polynomial. For example, the coefficient of in the second polynomial is , and there is way of making a sum of using only one element from the second set.
Now consider the product of the polynomials:
Before we expand out this product, let us consider what the coefficient of means in the polynomial product: it represents the number of ways of making a sum of taking exactly one number from each set. The expansion of the product is
Note that the coefficient of is for , since we cannot make a sum greater than using one from each set. The same goes for .
When , the coefficient is . This means that there are ways of making . If we expand the product fully using the distributive formula, we see that the three terms come from the products of with , with , and with .
The idea of attaching meaning to the coefficient of without attaching any meaning at all to is the idea of a generating function. A generating function encodes the numbers of objects using formal power series, which are polynomials with (possibly) infinitely many terms (of integer powers).
Note: The term formal is used because this is an algebraic concept, not an analytic concept.
In the above example, we could have simply counted the number of ways of making by inspection. However, generating functions are incredibly more useful if the polynomials may be expressed in a more compact form (such as using the geometric series sum), and then multiplication may lead to cancellation and an easier calculation.
Find the generating function for the face value of 1 die. Find the generating function for the sum of faces values of 2 dice.
For a standard six-sided die, there is exactly 1 way of rolling each of the numbers from 1 to 6. Hence, we can encode this as the power series . The exponents represent the value rolled on the die, and the coefficients represent the number of ways this value can be attained.
For rolling 2 dice, we could likewise list out the possible sums, and arrive at
A more direct method is to realize (from above) that , hence we can calculate it directly without having to count each individual term.
How many solutions in non-negative integers does the equation have?
First, we look at a more general question of finding the number of solutions in non-negative integers to the equation . Since the value of can be any non-negative integer (see note below), we can represent this as the generating function
We have the same generating function for the possible values of and . So our generating function for the number of solutions is . However, finding this product could be extremely tedious.
We instead transform into the rational function , which we recognize from the sum of a geometric progression. Thus, we are interested in . This can be expanded using the negative binomial theorem, which gives
Therefore, the answer when is given by . This agrees with what we know from the stars and bars method.
Note: It might be confusing why we allow to be any non-negative integer, even those which are larger than , which clearly would not lead to a solution. Consider what would happen if we let or or any larger integer: In the final product of polynomials, the exponents of these terms would be larger than so they will not contribute to the term we want, which has exponent
The question below can be solved by stars and bars, but it is tedious. We can solve it using generating functions.
Try this too:
Solving Homogeneous Linear Recurrence Relations
We begin by studying the problem of solving homogeneous linear recurrence relations using generating functions. In general, a recurrence relation for the numbers is a way of expressing in terms of previous terms in the sequence, for some positive integer A homogeneous linear recurrence relation is a relation of the form It is linear because each term has only a single monomial of the form and it is homogeneous because the righthand side is 0. If the right-hand side was a non-zero function of then it would be nonhomogeneous. To fully solve a recurrence relation, we require initial values for the first terms, where this is the same as the one in the definition.
Find explicitly where
and
Consider the generating function
Now, since we are given that , let's consider the function
Hence, we get which gives
Thus, by the negative binomial theorem or Taylor series, we can expand each of these terms, to conclude that
Thus, .
Let us generalize the above example. Suppose we have a sequence of numbers that satisfy the recurrence relation Then the terms of the recurrence are the coefficients of a generating function given by some rational function In particular,
where we have initial terms and the 's are defined as
We can use this to solve for explicitly by finding the roots of the denominator and taking the partial fractions decomposition of the rational function. We can solve for the coefficient of by applying the negative binomial theorem to each term. As such, we can conclude as follows:
For a recurrence relation with form as described above, we define the characteristic polynomial of the recurrence to be
Suppose our characteristic polynomial has roots with multiplicity for Then the general solution to the recurrence relation is
The constants are chosen to satisfy the initial conditions.
Notice that the total number of these constants is which is why we need initial values.
Solving Nonhomogeneous Linear Recurrence Relations
The change from a homogeneous to a non-homogeneous recurrence relation is that we allow the right-hand side of the equation to be a function of instead of So our recurrence relation is
Even with such a small change, the solutions become much more complicated.
Find where
and .
Consider the generating function
Now, since we are given that , let's consider the function
Hence, we get . This gives us
Thus, by the negative binomial theorem or Taylor series, we can expand each of these terms, to conclude that
Note: The typical approach to solving such a problem is to observe that if and are sequences that satisfy the recurrence, then satisfies the recurrence Note that this is the homogeneous version of the given recurrence which is easily solved. Hence, we just need to find a particular instance , and add it to the general form for .
Because we are merely manipulating a theoretical construct, we can actually apply many function operations to the generating functions that we created. For example, we can multiply them together, or even integrate and differentiate them termwise!
Find a closed form for
This example is simple enough that we could brute force out the solution. However, in the spirit of this wiki, let's solve this using generating functions.
Define
First, notice that can be defined in the form of , which is a convolution. This suggests that we should define the polynomials:
Then, we have . As such, by using the generating functions, we have
Hence, .
Increasing and Decreasing the Exponents of a Generating Function
When we have a generating function for a certain problem, we can manipulate it to solve other combinatorial problems.
Given some generating function , we can shift its coefficients positions to the right by multiplying it with
Using this technique of "shift method" gives us a clean solution to the following problem:
If you select exactly one element from , how many ways are there to select a given number? Express your answer as a simplified generating function.
As per the problem in the introduction, we will get a generating function where each term for every value in the set has a coefficient of 1:
This generating function is similar to the generating function in the introduction, except its coefficients have been shifted right by two spaces. Using this, we may express this generating function more succinctly as
Scaling the Exponents of a Generating Function
Given some generating function , we can scale its exponent by a factor of by composing it with the function :
Here is an example of the scale method:
If you select exactly one element from the set of even numbers , how many ways are there to select a given number?
Express your answer as a simplified generating function.
As per the problem in the introduction, we will get a generating function where each term for every even value has a coefficient of 1:
This generating function is similar to the generating function in the introduction, except each exponent has been doubled. Using the scale method, we can get a simple expression for the generating function by using :
Additional Problems
You have 10 different empty containers: 6 can contain up to 3 L of water and 4 can contain up to 8 L of water.
How many ways are there to fill up exactly 46 L of water into these containers, such that the number of liters of water in each container is an integer?
Details and Assumptions:
- The order of filling the containers is irrelevant.
- You cannot take water out from any of the containers.
- There are no spills.
The above shows the first few digits (actually 65) of the decimal representation of the fraction If we split the digits into partitions of 5, we can see that the numbers form a Fibonacci sequence: . How many positive Fibonacci numbers can we find before the pattern breaks off?
Note: For example, suppose that the fraction equals instead of the one given at the top. Then you could only find the first five Fibonacci numbers, namely . So your answer would then be that there are 4 positive Fibonacci numbers before the pattern breaks off.
- Bonus: Generalize this.
- Try Daniel Liu's problem that was inspired by this problem.
- Find explicitly, where and
- Find the general expression for , where
- Find the general expression for where
- Find explicitly, where Hint: consider
- Show that