Building OGFs for Integer Sequences

The Core Idea: From Sequences to Functions

At its heart, a generating function is a simple but brilliant idea: use a polynomial or power series as a "container" for a sequence of numbers. The coefficients of the series are the terms of the sequence, and the powers of a variable (say, $x$) act as placeholders to keep them in order.

For a sequence $a_0,a_1,a_2,\dots$, its ordinary generating function is the formal power series:
$G(x)=a_0{x}^0+a_1{x}^1+a_2{x}^2+a_3{x}^3+\cdots ={\sum }_{n=0}^{\infty }{a}_n{x}^n$
The term "formal" means we're not primarily concerned with whether this series converges to a number. We treat it as an algebraic object where the coefficients hold our combinatorial information.

This concept is explained beautifully in the following notes. The author uses an analogy of building words to show how multiplying polynomials naturally corresponds to combining objects and adding their properties (like length).

The Fundamental Building Block

The most important generating function, from which many others are derived, is the one for the constant sequence $1,1,1,\dots$. This corresponds to the geometric series:
$1+x+x^2+x^3+\cdots ={\sum }_{n=0}^{\infty }{x}^n=\frac{1}{1-x}$
This equality is the cornerstone of generating functions. We will call it our fundamental identity. By manipulating this single identity, we can construct generating functions for a vast number of other sequences.

The following video provides a clear, step-by-step guide to this fundamental identity and several essential manipulations.

(Note: The segment from 14:40-17:39 about derivatives is also a valid manipulation, but we will set it aside for now to focus on the more common algebraic constructions.)

Here is a summary of the key generating functions. Having these at your fingertips is incredibly useful.

Constructing Generating Functions for Combinatorial Problems

The true power of generating functions comes from translating combinatorial rules directly into algebra. The two most important rules are:

1. Disjoint Union (OR): If you can choose an object from set $A$ or from a disjoint set $B$, the generating function for the combined choices is $A(x)+B(x)$.
2. Cartesian Product (AND): If you construct an object by picking a part from set $A$ and a part from set $B$, the generating function for the composite object is $A(x)\cdot B(x)$.

This second rule is the magic key. When you multiply the polynomials, the exponents add ($x^i\cdot x^j=x^{i+j}$), which corresponds to combining the "weights" of the components. The coefficients multiply, which corresponds to the product rule for counting.

Let's see this in action. The following video demonstrates how to take a counting problem with constraints and build its generating function piece by piece.

Let's consolidate this with an example. Suppose we want to find the number of solutions to $e_1+e_2+e_3=n$ in non-negative integers, where:

• $e_1$ must be an even number.
• $e_2$ must be a multiple of 3.
• $e_3$ must be at least 1 and at most 4.

We construct a factor for each variable, where the exponents represent the possible values that variable can take.

• For $e_1$ (even): The possible values are 0, 2, 4, ... This gives the series $x^0+x^2+x^4+\dots$, which is a geometric series with ratio $x^2$. Its generating function is $E_1(x)=\frac{1}{1-x^2}$.
• For $e_2$ (multiple of 3): The possible values are 0, 3, 6, ... This gives the series $x^0+x^3+x^6+\dots$, a geometric series with ratio $x^3$. Its generating function is $E_2(x)=\frac{1}{1-x^3}$.
• For $e_3$ (1 $\le e_3\le$ 4): The possible values are 1, 2, 3, 4. This gives the finite polynomial $E_3(x)=x^1+x^2+x^3+x^4$. We can factor this as $x(1+x+x^2+x^3)$ and use the formula for a finite geometric sum: $x\frac{1-x^4}{1-x}$.

Since a solution requires a value for $e_1$ AND $e_2$ AND $e_3$, we multiply their generating functions to get the total generating function $G(x)$:

$G(x)=E_1(x)\cdot E_2(x)\cdot E_3(x)=\left(\frac{1}{1-x^2}\right)\left(\frac{1}{1-x^3}\right)\left(\frac{x(1-x^4)}{1-x}\right)$

The coefficient of $x^n$ in the full expansion of this $G(x)$ gives the number of solutions for a specific sum $n$. For today, our goal is simply to get to this point: constructing the function.

Practice Problems

Now it's your turn to build some generating functions. For each problem, your task is to write down the generating function whose coefficients would answer the question. You do not need to expand the function or find the final numerical answer.

1. Find the generating function for the number of ways to choose $n$ fruits from a basket containing apples, bananas, and oranges, such that you pick an even number of apples, a number of bananas that is a multiple of 3, and at most 2 oranges.

2. Find the generating function for the number of ways to distribute $n$ identical cookies to three distinct children (let's call them A, B, and C) such that child A gets at least 2 cookies, child B gets at most 4 cookies, and child C gets 1 or 3 cookies.

3. What is the generating function for the number of ways to make $n$ cents in change using pennies (1 cent), nickels (5 cents), and dimes (10 cents), if you must use an odd number of pennies and at least one dime?

Conclusion

Today, you've learned a new and profoundly useful way to represent combinatorial problems. We've seen that an entire sequence of numbers, representing the answers to a counting problem for all $n$, can be "packaged" into a single algebraic expression—an ordinary generating function. You learned how to construct these functions by translating constraints (like "even", "at most 4", "multiple of 5") into polynomial factors and combining them through multiplication.

We've focused entirely on the construction of these functions. You may be wondering how we get the final answer—the specific coefficient of $x^n$—out of a complicated expression like the ones we built. That is precisely the topic of our next lesson. We will explore techniques, such as partial fraction decomposition, to expand these compact functions back into power series, allowing us to read off the coefficients and solve the recurrence relations and counting problems that motivated us in the first place.