Ordinary Generating Function

The ordinary generating function (OGF) of a sequence $a$ is defined as the formal power series:

$$F(x)=\sum_{n}a_n x^n$$

$a$ may be either a finite sequence or an infinite sequence. Common examples (assuming that $a$ starts at $0$):

1. The ordinary generating function of the sequence $a=\langle 1,2,3\rangle$ is $1+2x+3x^2$.
2. The ordinary generating function of the sequence $a=\langle 1,1,1,\cdots\rangle$ is $\sum_{n\ge 0}x^n$.
3. The generating function of the sequence $a=\langle 1,2,4,8,16,\cdots\rangle$ is $\sum_{n\ge 0}2^nx^n$.
4. The generating function of the sequence $a=\langle 1,3,5,7,9,\cdots\rangle$ is $\sum_{n\ge 0}(2n+1)x^n$.

In other words, if sequence $a$ has a formula for its general term, then the coefficients of its ordinary generating function are given by that general-term formula.

Basic Operations

Consider the ordinary generating functions of two sequences $a,b$, denoted by $F(x),G(x)$, respectively. Then

$$F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n$$

Therefore, $F(x)\pm G(x)$ is the ordinary generating function of the sequence $\langle a_n\pm b_n\rangle$.

Consider multiplication, that is, convolution:

$$F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i}$$

Therefore, $F(x)G(x)$ is the ordinary generating function of the sequence $\langle \sum_{i=0}^n a_ib_{n-i} \rangle$.

Closed Forms

When using generating functions, we do not always work in the form of formal power series. Instead, we convert them to closed forms when appropriate to simplify the calculations.

For example, for $\langle 1,1,1,\cdots\rangle$, whose ordinary generating function is $F(x)=\sum_{n\ge 0}x^n$, we can observe that

$$F(x)x+1=F(x)$$

Solving this equation gives

$$F(x)=\frac{1}{1-x}$$

This is the closed form of $\sum_{n\ge 0}x^n$.

Consider the geometric sequence $\langle 1,p,p^2,p^3,p^4,\cdots\rangle$ and its generating function $F(x)=\sum_{n\ge 0}p^nx^n$. We have

$$\begin{aligned}F(x)px+1 &=F(x)\\F(x) &=\frac{1}{1-px}\end{aligned}$$

The closed form and expanded form of a geometric sequence are commonly used as transformation tools.

Small Exercises

Find the ordinary generating functions of the following sequences (in both formal power series form and closed form). The difficulty increases gradually.

1. $a=\langle 0,1,1,1,1,\cdots\rangle$.
2. $a=\langle 1,0,1,0,1,\cdots \rangle$.
3. $a=\langle 1,2,3,4,\cdots \rangle$.
4. $a_n=\binom{m}{n}$ ($m$ is a constant, $n\ge 0$).
5. $a_n=\binom{m+n}{n}$ ($m$ is a constant, $n\ge 0$).

Answers

The first:

$$F(x)=\sum_{n\ge 1}x^n=\dfrac{x}{1-x}$$

The second:

$$\begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned}$$

The third (by differentiation):

$$\begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned}$$

The fourth (by the binomial theorem):

$$F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m$$

The fifth:

$$F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}}$$

This can be proved by induction.

First, when $m=0$, we have $F(x)=\dfrac{1}{1-x}$.

When $m>0$, we have

$$\begin{aligned} \frac{1}{(1-x)^{m+1}} &=\frac{1}{(1-x)^m}\frac{1}{1-x}\\ &=\left(\sum_{n\ge 0}\binom{m+n-1}{n}x^n \right)\left(\sum_{n\ge 0}x^n \right)\\ &=\sum_{n\ge 0} x^n\sum_{i=0}^n \binom{m+i-1}{i}\\ &=\sum_{n\ge 0}\binom{m+n}{n}x^n \end{aligned}$$

Generating Function of the Fibonacci Sequence

Next, we derive the generating function of the Fibonacci sequence.

The Fibonacci sequence is defined by $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1)$. Let its ordinary generating function be $F(x)$. Then, based on its recurrence, we can similarly write an equation for $F(x)$:

$$F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0$$

Solving it gives

$$F(x)=\frac{x}{1-x-x^2}$$

The next question is: how do we find its expanded form?

Expansion Method One

We may treat $x+x^2$ as a single unit. Then we obtain

$$\begin{aligned} F(x) &= \dfrac{x}{1-(x+x^2)} \\ &= x\sum_{k=0}^{\infty}(x+x^2)^k \\ &= x\sum_{k=0}^{\infty}\sum_{i=0}^k\binom{k}{i}x^{k-i}(x^2)^i \\ &= \sum_{k=0}^{\infty}\sum_{i=0}^k\binom{k}{i}x^{k+i+1} \\ &= \sum_{n=1}^{\infty}\sum_{i=0}^{\lfloor(n-1)/2\rfloor}\binom{n-i-1}{i}x^n. \end{aligned}$$

In the last step, let $n=k+i+1$ and change the order of summation. Thus, we obtain the formula for the general term:

$$a_n = \sum_{i=0}^{\lfloor(n-1)/2\rfloor}\binom{n-i-1}{i}.$$

This is not the familiar form involving the golden ratio.

Expansion Method Two

Consider solving an equation with undetermined coefficients:

$$\frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2}$$

Putting the fractions over a common denominator gives

$$\frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2}$$

Equating the coefficients of the undetermined terms, we obtain

$$\begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases}$$

Solving gives

$$\begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases}$$

Then, using the expansion of a geometric sequence, we obtain the formula for the general term of the Fibonacci sequence:

$$\frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right)$$

This is also known as another closed form of the Fibonacci sequence (with $\frac{x}{1-x-x^2}$ being a closed form).

For any polynomials $P(x),Q(x)$, the expansion of the generating function $\dfrac{P(x)}{Q(x)}$ can be found using the method above. In practice, we usually first find the roots of $Q(x)$ and express the denominator in the form $\prod (1-p_ix)^{d_i}$, then determine the numerator terms.

When factoring the denominator, if there are repeated roots, each repeated root requires one more fraction. For example, consider the generating function

$$G(x)=\frac{1}{(1-x)(1-2x)^2}$$

For the formula for the general term of its coefficients, we have

$$G(x)=\frac{c_0}{1-x}+\frac{c_1}{1-2x}+\frac{c_2}{(1-2x)^2}$$

Solving gives

$$\begin{cases} c_0&=1\\ c_1&=-2\\ c_2&=2 \end{cases}$$

Therefore

$$[x^n]G(x)=1-2^{n+1}+(n+1)\cdot 2^{n+1}$$

Newton's Binomial Theorem

We redefine the operation of taking binomial coefficients:

$$\binom{r}{k}=\frac{r^{\underline{k}}}{k!}\quad(r\in\mathbf{C},k\in\mathbf{N})$$

Note that the range of $r$ is the complex field. In this case, for $\alpha\in\mathbf{C}$, we have

$$(1+x)^{\alpha}=\sum_{n\ge 0}\binom{\alpha}{n}x^n$$

The binomial theorem is actually a special case of Newton's binomial theorem.

Generating Function of the Catalan Numbers

Refer to Algebraic Derivation in Catalan Number Forms.

Applications

Next, we give some example problems to introduce concrete applications of generating functions in OI.

Food

Food

Choose $n$ items from several different kinds of food, subject to the following restrictions for each kind:

1. Chengde hamburgers: an even number
2. Cola: 0 or 1
3. Chicken legs: 0, 1, or 2
4. Peach Duo: an odd number
5. Chicken nuggets: a multiple of 4
6. Buns: 0, 1, 2, or 3
7. Stir-fried pork with potato slices: at most one.
8. Bread: a multiple of 3

Each kind of food is counted in units of “items”; a selection is considered one way whenever the total number of items is $n$. For a given $n$, calculate the number of ways modulo $10007$.

This is a classic generating-function problem. For one kind of food, let $a_n$ denote the number of ways to choose $n$ items of that kind, and find its generating function. The generating function for the number of ways to choose a total of $n$ items from two kinds of food is the convolution of their generating functions. For multiple kinds of food, the generating function for the number of ways to choose a total of $n$ items is likewise the convolution of their generating functions.

Once we understand that the number of ways can be represented by convolution, we can construct the generating functions (the labels correspond to the food labels in the problem):

1. $\displaystyle\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}$.
2. $1+x$.
3. $1+x+x^2=\dfrac{1-x^3}{1-x}$.
4. $\dfrac{x}{1-x^2}$.
5. $\displaystyle \sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}$.
6. $1+x+x^2+x^3=\dfrac{1-x^4}{1-x}$.
7. $1+x$.
8. $\dfrac{1}{1-x^3}$.

Multiplying them all together gives the generating function for the answer:

$$F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)} =\frac{x}{(1-x)^4}$$

Then convert it into expanded form (using the fifth exercise from the closed-form exercises):

$$F(x)=\sum_{n\ge 1}\binom{n+2}{n-1}x^n$$

Therefore, the answer is $\dbinom{n+2}{n-1}=\dbinom{n+2}{3}$.

Sweet

「CEOI2004」Sweet

There are $n$ piles of candy. The candies in different piles are of different kinds (that is, all candies in the same pile are of the same kind, and candies in different piles are of different kinds). The $i$-th pile contains $m_i$ candies. You must eat at least $a$ candies but no more than $b$ candies. Find the number of ways to do so.

Two ways are different if and only if the numbers of candies eaten differ, or the number of candies of some kind among the candies eaten differs between the two ways.

$n\le 10,0\le a\le b\le 10^7,m_i\le 10^6$.

For pile $i$, the generating function for the number of ways to eat $j$ candies (which is clearly 1) is

$$F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x}$$

Therefore, the generating function for the number of ways to eat a total of $i$ candies is

$$G(x)=\prod_{i=1}^n F_i(x)=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1})$$

What we need is $\sum_{i=a}^b[x^i]G(x)$.

Since $n\le 10$, we can expand $\prod_{i=1}^n(1-x^{m_i+1})$ by brute force (there are at most $2^n$ terms).

Then apply Newton's binomial theorem to $(1-x)^{-n}$:

$$\begin{aligned} (1-x)^{-n} &=\sum_{i\ge 0}\binom{-n}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{n-1+i}{i}x^i \end{aligned}$$

In $\prod_{i=1}^n(1-x^{m_i+1})$, enumerate the coefficient of the $x^k$ term and suppose it is $c_k$. After multiplying it by $(1-x)^{-n}$, its contribution to the answer is

$$c_k\sum_{i=a-k}^{b-k}\binom{n-1+i}{i}=c_k\left( \binom{n+b-k}{b-k}- \binom{n+a-k-1}{a-k-1} \right)$$

Thus, the answer can be computed in $O(b)$ time.

The time complexity is $O(2^n+b)$.