Solution by Method of Generating Functions

Definition

A generating function for a sequence $\{a_0, a_1, a_2, \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$, and it usually represents the number of ways a combinatorial object of size $n$ can occur.

In combinatorics, generating functions are not primarily treated as ordinary functions for numerical evaluation, but as formal algebraic tools. The main idea is:

• encode a sequence into a series,
• manipulate the series algebraically,
• extract coefficients to obtain the required answer.

A common version used in combinatorics is the ordinary generating function (OGF).

Main Content

1. First Concept: Ordinary Generating Functions

Definition and meaning

If a sequence is $a_0, a_1, a_2, \dots$, then its ordinary generating function is
$$A(x)=\sum_{n=0}^{\infty} a_n x^n$$ Here, the coefficient of $x^n$ stores the value of the sequence at position $n$.

How it is used in counting

Suppose a combinatorial problem asks for the number of ways to make a total $n$ using available choices. Each choice is represented by a factor in a polynomial or series. When these factors are multiplied, the coefficient of $x^n$ in the final product gives the number of possible ways.

Example:
If an item can be chosen in 0, 1, or 2 copies, then the generating function is: $$1 + x + x^2$$ If there are two such items, then the total generating function is: $$(1+x+x^2)^2$$ The coefficient of $x^3$ gives the number of ways to get total 3 units from the two items.

2. Second Concept: Coefficient Extraction and Series Manipulation

Coefficient extraction

The central task in generating functions is to find the coefficient of a particular power of $x$. If $$F(x)=\sum_{n=0}^{\infty} a_n x^n,$$ then $[x^n]F(x)=a_n$, meaning “the coefficient of $x^n$ in $F(x)$.”

Algebraic operations on generating functions

Different combinatorial rules correspond to different algebraic operations:

• Addition represents alternatives.
• Multiplication represents combined independent choices.
• Exponentiation often represents repeated selections or structured arrangements.

A key fact is that multiplying generating functions performs convolution of sequences.

If $$A(x)=\sum_{n\ge0} a_n x^n,\quad B(x)=\sum_{n\ge0} b_n x^n,$$ then $$A(x)B(x)=\sum_{n\ge0}\left(\sum_{k=0}^{n} a_k b_{n-k}\right)x^n$$ So the coefficient of $x^n$ in the product counts all ways to split the total $n$ between two components.

Example:
To count the number of ways to obtain sum 4 using numbers from two independent sources, multiplication of their generating functions automatically combines the possibilities.

3. Third Concept: Solving Recurrence Relations

Recurrence relations and generating functions

Generating functions are extremely effective for solving recurrences such as: $$a_n = a_{n-1} + a_{n-2}$$ with initial conditions, or more complicated linear recurrences.

Method idea

Define $$A(x)=\sum_{n=0}^{\infty} a_n x^n$$ Then multiply the recurrence by $x^n$, sum over all $n$, and express the resulting equation in terms of $A(x)$. After algebraic simplification, solve for $A(x)$, and then extract coefficients.

Example: Fibonacci sequence
Let $$F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}\quad (n\ge2)$$ Define $$F(x)=\sum_{n=0}^{\infty} F_n x^n$$ Then: $$F(x)=x+xF(x)+x^2F(x)$$ So, $$F(x)=\frac{x}{1-x-x^2}$$ This generating function encodes the Fibonacci sequence, and the coefficients of its expansion give the Fibonacci numbers.

Working / Process

1. Formulate the combinatorial problem as a sequence or recurrence

• Identify what quantity is being counted.
• Determine whether the problem gives a recurrence relation, a restriction-based counting task, or a partition/selection problem.
• Translate the information into a sequence $\{a_n\}$, where $a_n$ is the number of ways to obtain size $n$.

2. Construct the generating function

• Write the ordinary generating function: $$A(x)=\sum_{n=0}^{\infty} a_n x^n$$

• For counting problems, represent each allowed choice by a series factor.

• For recurrence problems, multiply the recurrence by $x^n$, sum over all applicable $n$, and rewrite everything in terms of $A(x)$.

3. Manipulate algebraically and extract coefficients

• Simplify the expression for the generating function.
• Factor, expand, or perform partial fractions if needed.
• Find the coefficient of the required power of $x$, which gives the answer to the original problem.

Example process:

Suppose we want the number of ways to form 5 using unlimited 1s and 2s.

• A 1 can be used any number of times: $$1+x+x^2+x^3+\cdots = \frac{1}{1-x}$$

• A 2 can be used any number of times: $$1+x^2+x^4+x^6+\cdots = \frac{1}{1-x^2}$$

• Total generating function: $$\frac{1}{(1-x)(1-x^2)}$$

• The coefficient of $x^5$ gives the number of ways to make 5.

Here the relevant combinations are: $$5,\ 3+2,\ 2+2+1,\ 1+1+1+1+1$$ So the answer is 4.

Advantages / Applications

Simplifies complex counting problems

Problems involving restrictions, repeated choices, or multiple cases can often be reduced to a clean algebraic formula.

Solves recurrence relations systematically

Many linear recurrences become easier to handle using generating functions, especially when initial values are given.

Useful in many combinatorial areas

Generating functions are applied in partition theory, integer compositions, graph enumeration, binomial identities, and discrete probability.

Summary

• Generating functions encode sequences into power series.
• They help solve counting problems and recurrence relations by algebraic manipulation.
• Coefficients of powers of $x$ give the required counts.
• Important terms to remember: sequence, ordinary generating function, coefficient extraction, recurrence relation, formal power series