Generating Functions

Definition

A generating function for a sequence $a_0, a_1, a_2, a_3, \dots$ is a formal power series of the form

$$G(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots=\sum_{n=0}^{\infty} a_n x^n$$

where:

• $a_n$ is the coefficient of $x^n$
• the sequence is encoded inside the coefficients
• the variable $x$ is usually treated as a formal symbol rather than a number in many combinatorial applications

For example, the sequence $1,1,1,1,\dots$ has generating function

$$1+x+x^2+x^3+\cdots=\frac{1}{1-x}, \quad |x|<1$$

This means the coefficients of the expansion of $\frac{1}{1-x}$ are all 1.

A generating function is most commonly used as a counting device: the coefficient of $x^n$ tells us how many objects of size $n$ exist in the combinatorial problem.

Main Content

1. Ordinary Generating Functions

Definition and meaning

• An ordinary generating function (OGF) for a sequence $\{a_n\}$ is $\sum_{n\ge 0} a_n x^n$. It is the standard form used in combinatorics when the order of objects matters only through the index $n$, not through extra labeling.

Examples and interpretation

• The sequence $1,1,1,\dots$ has OGF $\frac{1}{1-x}$.
• The sequence $1,2,3,4,\dots$ has OGF $\frac{1}{(1-x)^2}$.
• The sequence $1,3,6,10,\dots$ has OGF $\frac{1}{(1-x)^3}$.

These examples show how familiar sequences can be encoded compactly.

Why it is useful

Ordinary generating functions help in:

• counting combinations and selections,
• solving recurrence relations,
• finding closed forms for sequences,
• analyzing partitions and compositions.

Example

Suppose we want the number of ways to choose any number of objects from a set where each choice contributes a weight $x$. The generating function for “choose 0 or 1 of an object” is: $$1+x$$ If we have 3 independent objects, the total generating function becomes: $$(1+x)^3$$ The coefficient of $x^k$ gives the number of ways to choose $k$ objects.

2. Operations on Generating Functions

Addition and subtraction

If $A(x)=\sum a_n x^n$ and $B(x)=\sum b_n x^n$, then $$A(x)+B(x)=\sum (a_n+b_n)x^n$$ This means generating functions can combine sequences term by term.

Multiplication and convolution

If $$A(x)=\sum a_n x^n,\quad B(x)=\sum b_n x^n$$ then $$A(x)B(x)=\sum_{n=0}^\infty \left(\sum_{k=0}^n a_k b_{n-k}\right)x^n$$ The coefficient of $x^n$ becomes a convolution of the two sequences.

Shift property

Multiplying by $x^m$ shifts the sequence: $$x^mA(x)=a_0x^m+a_1x^{m+1}+a_2x^{m+2}+\cdots$$ This is useful for expressing recurrences.

Example

Let $A(x)=1+x+x^2+\cdots=\frac{1}{1-x}$. Then $$(1+x+x^2+\cdots)^2$$ has coefficient of $x^n$ equal to $n+1$. This counts the number of ways to write $n$ as a sum of two nonnegative integers: $$n=a+b$$ where $a,b\ge 0$.
For example, for $n=3$, the pairs are: $$(0,3),(1,2),(2,1),(3,0)$$ giving 4 ways.

3. Applications in Combinatorics and Recurrences

Counting combinatorial objects

Generating functions are used to count:

• binary strings,
• partitions of integers,
• paths in graphs and grids,
• ways to distribute objects with restrictions.

Solving recurrence relations

Many recurrences become algebraic equations after translating them into generating functions. For example, if $$a_n=a_{n-1}+a_{n-2}$$ then the generating function can be used to derive the Fibonacci sequence formula.

Example: Fibonacci sequence

Let $$F(x)=\sum_{n=0}^\infty F_n x^n$$ where $F_0=0, F_1=1$, and $F_n=F_{n-1}+F_{n-2}$.
Then: $$F(x)=x+xF(x)+x^2F(x)$$ Solving gives: $$F(x)=\frac{x}{1-x-x^2}$$ This compact expression encodes all Fibonacci numbers.

Counting with restrictions

Suppose we want the number of ways to make $n$ using coins of values 1, 2, and 5 with unlimited supply. The generating function is: $$(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots)$$ The coefficient of $x^n$ gives the number of ways to make $n$.

Working / Process

1. Write the sequence or counting problem as a power series

• Identify what the coefficient of $x^n$ should represent.
• Choose ordinary generating functions for ordinary counting problems.
• Example: if there are $a_n$ objects of size $n$, write $\sum a_n x^n$.

2. Use algebraic manipulation to express the problem

• Convert restrictions into factors.
• Use addition for alternative choices and multiplication for independent choices.
• Translate recurrences into equations involving the generating function.
• Example: a choice of 0, 1, 2, or more of an item can be written as $$1+x+x^2+\cdots=\frac{1}{1-x}$$

3. Extract coefficients and interpret the result

• Expand the function or simplify it into a known form.
• Find the coefficient of the required power of $x$.
• Interpret that coefficient as the answer to the counting problem or recurrence.
• Example: $$\frac{1}{(1-x)^2}=1+2x+3x^2+4x^3+\cdots$$ so the coefficient of $x^n$ is $n+1$.

Advantages / Applications

• Generating functions convert difficult counting problems into algebraic problems, making them easier to solve.
• They provide closed-form expressions for sequences and recurrence relations, including classical sequences like Fibonacci numbers.
• They are widely used in combinatorics, number theory, probability, computer science, and discrete structures.
• They help count partitions, compositions, lattice paths, and distributions with constraints.
• They reveal hidden patterns in sequences and support systematic problem-solving in discrete mathematics.

Summary

• Generating functions encode sequences as power series.
• Coefficients of powers of $x$ represent counted values.
• They are especially useful for combinatorial counting and recurrence solving.
• Important terms to remember: ordinary generating function, coefficient, power series, recurrence relation, convolution, sequence.