Overview

When solving combinatorial problems, it may be hard to brute-force or manipulate case-work by using words. By using generating functions, you can translate the words and descriptions into algebraic objects , which can help you easily manipulate them. Even simple applications can simplify counting and recurrence problems.

Key Ideas

• The coefficient of $x^n$ in $(1+x+x^2+\cdots)^k$ counts solutions to $x_1+\cdots+x_k=n$ with nonnegative integers.
• Finite options become finite polynomials like $(1+x+x^2)$.
• Multiplying series corresponds to combining choices.

Core Skills

Notation

When you want to extract the $x^n$ coefficient of the generating function $F(x)$, use the notation $[x^n]\ F(x)$

Translate Choices to Factors

Each variable contributes a factor $(1+x+x^2+\cdots)$ or a finite polynomial depending on constraints.

Extract Coefficients

Use known expansions like $(1-x)^{-k}$ or binomial coefficients to read off coefficients.

Use the geometric series: $1+x+x^2+x^3+\cdots=\frac{1}{1-x}$.

Use Truncation

When only low-degree terms matter, ignore higher powers after expansion. For example, when you want the coefficient of the term $x^3$, you can ignore multiplying by $x^4$ as it will only produce powers $\ge 4$.

Representations

Represent numbers such as cost or amount in the power. (e.g. an apple that costs 50 is represented as $x^{50}$)

Recurrence Formula (ADVANCED)

When given a recurrence formula that is to be solved by using generating functions, use the following method:

1. Make sure that the values of the variable (e.g. $n$) such that the recurrence relation is true, is clearly described.

2. Give a name to the generating function that you will look for, andwrite out that function in terms of the unknown sequence (e.g., call it $A(x)=\sum_{n > 0} a_nx^n$).

3. Multiply both sides of the recurrence by $x^n$, and sum over all values of $n$ for which the recurrence holds.

4. Express both sides of the resulting equation explicitly in terms of your generating function $A(x)$.

5. Solve the resulting equation for the unknown generating function $A(x)$.

6. If you want an exact formula for the sequence that is defined by the given recurrence relation, then attempt to get such a formula by expanding $A(x)$ into a power series by any method you can think of. In particular, if $A(x)$ is a rational function (quotient of two polynomials), then success will result from expanding in partial fractions and then handling each of the resulting terms separately.

Worked Example

Count solutions to $a+b+c=5$ with $a,b,c\ge0$.

The generating function is $(1+x+x^2+\cdots)^3=\frac{1}{(1-x)^3}$. The coefficient of $x^5$ is $\binom{5+3-1}{3-1}=21$.

(Brute Force Method: Since we only need the $x^5$ term, we can let the 'generating function' as $(1+x+x^2+x^3+x^4+x^5)^3$ and then brute force expand this. NOT RECOMMENDED)

More Examples

Example 1: Bounded Variables

Count solutions to $x+y+z=4$ with $0\le x,y,z\le 2$.

Use $(1+x+x^2)^3$ and extract the $x^4$ coefficient.

Example 2: Distinct Parts

Count partitions of $n$ into distinct parts.

Use the generating function $\prod_{k \ge 1}(1+x^k)$.

Example 3: Counting Word Problem

Alice went to a store and saw three items: an apple (cost: 9 cents), a banana (cost: 14 cents), and an orange (cost: 17 cents). She has exactly 2 dollars and doesn't want any change. In how many ways can she achieve this?

Convert this problem into equations: let $x$ be the number of apples, $y$ be the number of bananas, $z$ be the number of oranges. Then $x, y, z \ge 0$. So constraints is $9x + 14y + 17z = 200$. So we wish to find the $x^{200}$ coefficient of

Example 4: Recurrence Extraction (ADVANCED)

Find the general term of $f_{n+1}=f_n+f_{n-1}$ where $n \ge 1, f_0 = 0, f_1 = 1$

By using the above method, we let $F(x) = \sum_{n \ge 0} f_nx^n$ By manipulating the given recurrence relation (multiply by $x^n$ and sum over $n \ge 1$),

Remember that $f_0 = 0$ and $f_1 = 1$.

Then,

By manipulating this, we get:

By doing partial fractions, we can let this be:

Where $\alpha = \frac{1+\sqrt{5}}{2}$ and $\beta = \frac{1-\sqrt{5}}{2}$ (Notice that $\alpha = \phi$, the golden ratio). Now, using the geometric series $\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$.

By substituting the values of $\alpha$ and $\beta$,

When comparing this to Binet's formula for Fibonacci numbers, this is equal to

Example 5: Interesting Sum

Your goal is to evaluate the following expression:

First, we let

Then

Using

we get that

And factoring,

Then, we see that partial fractions gives us the following:

And consequently,

Example 6: Classic Gen. Functions Problem (remember this!)

Let $a_n$ denote the number of ordered compositions of $n$ whose parts are only $1,2,$ or $4$. Your job is to find $a_n$.

First, notice that each part contributes the following:

Thus, we have that

Next, we can multiply through to get:

And comparing the coefficients gives us our answer:

Example 7: Only Even-Sized Subsets (also very common! Remember this!)

How many subsets of $\{1,2,\dots,n\}$ contain an even number of elements (solve using generating functions)?

First, notice that the generating function is simply:

Realize that the sum of the even coefficients is

And consequently, we get

Which makes the answer:

Example 8: More binomial expressions!

Your job is to show that the following expression is true:

First, recall that

Then, squaring the expression, we get:

Notice that the coefficient of $x^n$ on the left is simply

while the coefficient on the right is

Thus, we have:

Example 9: Catalan Numbers (very famous and fun numbers with many applications!)

Your goal is to find a generating function for the Catalan numbers $C_n$, which are defined by

First, we let

Then, using the recurrence relation, we get that

Solving the quadratic equation,

Since $C(0)=1$, we can simply choose the negative one

Thus,

Example 10: Derangements

Let $d_n$ denote the number of permutations of $\{1,2,\dots,n\}$ with no fixed points.

First, notice that the exponential generating function for all permutations is

Next, notice that for each element, either it is fixed (contributing $x$) or not fixed (contributing $1$), so we can simply remove fixed points by multiplying by $e^{-x}$.

Hence the exponential generating function for derangements is

Therefore,

Strategy Checklist

• Translate each constraint into a factor.
• Use binomial series for $(1-x)^{-k}$.

  • Use the geometric series $1+x+x^2+\dots = \frac{1}{1-x}$.
• Truncate when only a few coefficients are needed.
• Convert the amount of an item into a power of $x$.
• Use the above 'method' to solve for the recurrence relation.

  1. Describe variables
  2. Name Generating Functions
  3. Sum over all $n$ that the relation holds
  4. Express equation in generating functions from Step 2
  5. Solve equation
  6. Expand generating function into power series to extract coefficients.

(This module was based on generating functionology: https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf )

Practice Problems