7. Ordinary generating functions: definitions and series multiplication#
In rook polynomials, we used polynomials as an efficient bookkeeping tool to record the number of ways to place nonattacking rooks on a board. The polynomial packaged the counts for rooks into a single algebraic expression. Instead of computing each coefficient separately, we manipulated the polynomial as a whole.
This bookkeeping idea is the foundation of generating functions. Many fundamental combinatorial problems depend on a nonnegative integer parameter , measuring the size or value of an object. Instead of calculating each count in isolation, we assemble the entire sequence of counts into a single series: This series is the ordinary generating function of the sequence. The variable is not a numerical quantity to be approximated or evaluated; it is a placeholder whose exponent records the size or value of the object, while the coefficient records how many objects of that size exist.
After studying these notes, you will be able to do the following.
Define the ordinary generating function of a sequence and identify the combinatorial meaning of its exponents and coefficients.
Recover specified counts from a generating function using the coefficient extraction operator.
Translate coin selections and change-making problems with finite and infinite supplies into polynomial and series products.
Substitute variables to count aggregate quantities such as monetary value rather than raw item counts.
Multiply formal power series and explain the Cauchy product algebraically, combinatorially, and via nested loops.
Model selections with parity constraints, upper bounds, and combinations with repetition using series multiplication.
7.1 Packaging sequences into generating functions#
When we have a sequence of combinatorial numbers associated with a parameter , we can construct a generating function that stores all of them at once.
Definition 1 (Ordinary generating function and coefficient extraction)#
The ordinary generating function (abbreviated OGF) of a sequence is the formal power series For each integer , the notation denotes the coefficient of in . Therefore, .
The variable is as an algebraic indeterminate – a label for the th position in the sequence. If the sequence is zero from a certain onwards, the generating function is a finite sum, that is a polynomial: In any case, both polynomial and infinite power series, we do not concern ourselves whether the series converges or defines a function.
Warning (Do not swap exponents and coefficients)#
The exponent represents the parameter being counted (such as size, length, or monetary value), whereas the coefficient represents the number of objects with that parameter. Writing instead of reverses their roles and defines an entirely different sequence. Always make sure the power of matches the parameter being tracked.
Let us examine four basic examples to see how combinatorial questions translate into generating functions.
Example 2 (Subsets of an -element set)#
How many subsets of an -element set are there? For , the answers are respectively: For an arbitrary universe set of elements, each element may independently be included or excluded from a subset. By the product rule, there are subsets. When , the universe set is the empty set , which has exactly one subset: the empty set itself.
The ordinary generating function for the sequence of subset counts is The exponent carries the size of the universe set , and the coefficient carries the number of subsets:
Example 3 (Choosing items from a fixed finite set)#
How many ways are there to choose items from a set of distinct items, if order does not matter?
Solution: An unordered selection of items from distinct items without repetition is an -element combination, counted by the binomial coefficient . Evaluating these for : By symmetry of combinations, , , , , and . For any , it is impossible to choose more items than are present in the set, so .
Because the sequence is zero for all , the generating function is a finite polynomial: From the Binomial Theorem, we recognize that this polynomial is the expansion of .
Example 4 (Choosing identical coins from a single pile)#
Suppose you have in front of you a pile containing an unlimited supply of identical coins. How many ways can you choose coins from this pile?
Solution: Because all the coins are identical, two selections of coins cannot be distinguished. The only decision is how many coins to pick up. For any integer , there is exactly way to choose coins: pick up of them.
The sequence of counts is , and its ordinary generating function is Every coefficient is : for all .
The generating function appears very simple, but it is one of the most fundamental building blocks in combinatorics.
Example 5 (Tracking monetary value instead of coin count)#
Now suppose you have a pile of dimes, and instead of counting the number of coins you take, you want to track the total monetary value in cents that you obtain. How do we write a generating function for this?
Solution: In the generating function the monomial records choosing coins. But one dime has a monetary value of cents, not cent. Choosing dimes yields a total value of cents.
To track value rather than coin count, we replace with . Each term is replaced by . The power of now records the total value in cents: The coefficient of in this series is if the value can be formed by dimes (which occurs precisely when is a multiple of ), and otherwise:
This still looks like a needlessly complicated way of keeping track of something quite simple.
Next, we will see how to use this idea to keep track of the value obtained by electing coins from several piles of different denominations. The total value is going to be the sum of the values contributed by each type of coin. Next we examine how and why multiplication records this combined selections.
7.2 Selecting multiple coins and polynomial multiplication#
Suppose we have three piles of different coins:
pennies,
nickels,
dimes.
We may choose any number of pennies from to , any number of nickels from to , and any number of dimes from to . We start by representing the choices for each pile using distinct algebraic variables: for pennies, for nickels, and for dimes.
For pennies:
For nickels:
For dimes:
In each polynomial, the exponent of the variable records the number of coins of that denomination selected. For example, represents choosing pennies, and the constant term represents choosing pennies.
What happens if we multiply these three polynomials together? By the distributive law of elementary algebra, expanding this product requires forming every possible product of three terms—one term from the first factor, one from the second, and one from the third: There are choices for , choices for , and choices for , producing terms. The complete ungrouped expansion is arranged in blocks according to the power of : Thus every monomial with , , and occurs once, with no terms omitted or grouped. Notice an essential combinatorial fact: every single monomial appears with coefficient , and each monomial corresponds to a unique selection of coins consisting of exactly pennies, nickels, and dimes.
7.2.1 Tracking monetary value by substitution#
Now suppose we want to count the total monetary value in cents of each selection. A penny is worth cent, a nickel is worth cents, and a dime is worth cents. To record monetary value, we replace each coin variable with a power of a single variable matching its denomination: Under this substitution, the monomial becomes The exponent is precisely the total monetary value of the selection in cents.
Before collecting terms, let us look at how individual selections map to powers of :
Different selections can have the same total value. After substituting powers of , the coefficient of a power of records how many selections have that value. The expanded polynomial below lets Sage perform that collection of like terms.
7.2.2 Substituting before expanding#
We do not need to expand the product in three variables first and substitute later. Because multiplication and substitution commute, we substitute , , and directly into the factors before multiplying:
The answer to how many ways we can make change for cents is simply the coefficient of in their product:
Let us summarize this discussion in a self-contained problem and solution.
Problem 6 (Making change with bounded coin supplies)#
A coin purse contains at most pennies, nickels, and dimes.
Find the ordinary generating function for the number of ways to make change for cents using coins from this purse.
Find the number of ways to make change for cents.
Solution:
Each coin denomination provides an independent choice of how many coins to use, bounded by the supply in the purse:
Pennies contribute a value , represented by .
Nickels contribute a value with , represented by .
Dimes contribute a value with , represented by .
Because the total value is the sum of the values from each coin type, the generating function for the number of ways to make change for cents is the product: The coefficient gives the number of ways to make change for cents.
The following code expands the generating function in SageCell.
t = var('t') P(t) = 1 + t + t^2 + t^3 + t^4 + t^5 + t^6 + t^7 + t^8 N(t) = 1 + t^5 + t^10 + t^15 + t^20 + t^25 + t^30 D(t) = 1 + t^10 + t^20 + t^30 + t^40 C(t) = P(t)*N(t)*D(t) show( C(t).expand() )
The call to
C(t).expand()returns Thus the coefficient of is .If the expanded polynomial is too long to display, first expand it and then extract the requested coefficient:
show( C(t).expand().coefficient(t, 12) )
7.2.3 Infinite generating functions: unlimited supplies#
What changes if we have an unlimited supply of coins of each denomination?
Problem 7 (Making change with unlimited coin supplies)#
Find the generating function for the number of ways to make change for cents using an unlimited supply of pennies, nickels, and dimes.
Solution: Because there is no upper limit on the number of coins of any type, the choices for each denomination run over all nonnegative integers . Each factor becomes an infinite series:
The generating function for the number of ways to make change for cents is their product: The coefficient is the number of nonnegative integer solutions to Although each factor in is an infinite series, computing any specific coefficient requires adding only finitely many terms. To find the coefficient of , truncate each factor at degree ; terms of larger degree cannot affect it. This SageCell code expands the resulting polynomial:
t = var('t')
P(t) = 1 + t + t^2 + t^3 + t^4 + t^5 + t^6 + t^7 + t^8 + t^9 + t^10 + t^11 + t^12
N(t) = 1 + t^5 + t^10
D(t) = 1 + t^10
C(t) = P(t)*N(t)*D(t)
show(
C(t).expand()
)
The output is Thus the coefficient of is .
Because each coefficient involves only a finite number of arithmetic operations, we do not need to evaluate the series at any real number or discuss limits and convergence.
7.3 The algebra of series and the Cauchy product#
We have seen that multiplying generating functions corresponds to combining independent choices and adding their sizes or values. Let us now examine how the multiplication of two infinite power series is defined algebraically.
Let and be two formal power series. When we multiply and , every term in multiplies every term in :
7.3.1 Double sums and commuting summations#
The double sum instructs us to sum the product over all pairs of nonnegative integers . We can organize these terms into a two-dimensional grid:
Summing row by row corresponds to evaluating Summing column by column corresponds to evaluating Both orders sum the exact same collection of terms. In formal power series, the order of summation can be commuted freely because at any degree , only the finitely many pairs satisfying contribute to the coefficient of .
7.3.2 Grouping by degree: the anti-diagonals#
To write the product as a standard formal power series , we collect all terms in the grid that have the same total exponent of . The power of in cell is . The cells where lie along the th anti-diagonal of the grid:
Degree : . The coefficient is .
Degree : . The coefficient is .
Degree : . The coefficient is .
Degree : . The coefficient is .
In general, for a fixed degree , as the index runs from to , the index must be . Therefore: We can write this diagonal regrouping in two equivalent notations: The notation means: sum the product over all pairs of nonnegative integers and whose sum is .
7.3.3 Nested loops analogy in programming#
This change in the order of summation is familiar from computer programming. Suppose we want to compute the array of coefficients for the product of two polynomials up to degree .
The first method corresponds to two independent nested loops over the indices and :
# Approach 1: Double loop over independent indices j and k
for j from 0 to N:
for k from 0 to N - j:
C[j + k] = C[j + k] + A[j] * B[k]
In this approach, every pair is visited, and the product is accumulated into the bucket .
The second method groups the work by the target degree first:
# Approach 2: Outer loop over the target degree n
for n from 0 to N:
C[n] = 0
for j from 0 to n:
C[n] = C[n] + A[j] * B[n - j]
Both algorithms perform the exact same multiplications and produce the exact same array . The second approach computes each coefficient directly as a single sum over .
Definition 8 (Cauchy product)#
Let and be formal power series. Their Cauchy product is the formal power series where each coefficient is defined by The sequence is called the convolution of the sequences and .
7.4 Selections with conditions and combinatorial models#
We can now use the algebra of series to model a variety of combinatorial problems where individual components must satisfy specified conditions.
Example 9 (Climbing stairs with strides of 1 or 2 steps)#
A student climbs a flight of stairs. In each stride, the student may climb either step or steps.
Find the polynomial that represents the number of steps taken in a single stride.
Find the generating function for the number of steps climbed in strides.
How many ways can the student climb steps in exactly strides?
Solution:
A single stride can cover either step or steps. We assign the exponent to the number of steps covered, giving the polynomial The term records taking step, and records taking steps.
In strides, the total number of steps climbed is the sum of the steps taken in stride , stride , and so on through stride . By the product rule, the generating function for the total steps in strides is the th power of :
To find the number of ways to climb steps in exactly strides, we extract the coefficient of in :
The coefficient of is : .
The ways to climb steps in strides correspond to the ordered sequences of strides: Each sequence has strides and total sum steps.
Example 10 (Even pennies and at most two nickels)#
How many ways can we make change for cents using pennies, nickels, and dimes if we must use an even number of pennies, at most 2 nickels, and an unlimited supply of dimes?
Solution: We formulate a generating function in the variable , where the exponent records the total value in cents:
Even number of pennies: The allowed coin counts are . Since each penny is cent, the value contributed is cents, giving the series
At most 2 nickels: We may choose nickels. The values contributed are cents, giving the polynomial
Unlimited dimes: The allowed counts are dimes, contributing multiples of cents:
The generating function for making change under these constraints is their product: We want to determine the coefficient , which counts the number of integer solutions to Notice that , , and are all even integers. Therefore, must also be even. This forces to be even. Because , the only possibilities are or :
Case ( nickels, cents): The equation becomes , which simplifies to :
If : ( pennies, dimes).
If : ( pennies, dime).
If : ( pennies, dimes).
This gives valid combinations.
Case ( nickels, cents): The equation becomes , so , which simplifies to :
If : ( pennies, dimes).
If : ( pennies, dime).
This gives valid combinations.
No solutions exist for ( nickel) because cents from a nickel leaves cents to be formed by dimes and an even number of pennies, which can only produce an even total.
Adding the two cases gives ways to make cents: .
Example 11 (Combinations with repetition from 3 types of objects)#
Consider the product of three identical geometric series: What combinatorial quantity does the coefficient of count?
Solution: When we expand this product, choose from the first factor, from the second factor, and from the third factor. The resulting monomial is The Cauchy product therefore gives Thus Each summand corresponds to one triple of selected quantities. Equivalently, it corresponds to one multiset of size chosen from three distinct types, with , , and objects chosen from the first, second, and third types, respectively.
7.4.1 Looking forward: closed forms and algebraic operations#
Writing series as expanded sums like is clear and direct, but performing algebraic manipulations by expanding factors term by term becomes cumbersome for larger problems.
In calculus, we know that the geometric series can be written compactly as the fraction . Can we treat generating functions as algebraic fractions in combinatorics without concerning ourselves with convergence? How do we expand powers like or products like into explicit coefficient formulas?
Next, we develop the formal algebra of rational generating functions, prove closed-form formulas for standard series, and establish systematic tools for coefficient extraction.