Skip to content

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\) can be either a finite or an infinite sequence. Common examples (assuming \(a\) starts from index \(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 the sequence \(a\) has a general term formula, then the coefficients of its ordinary generating function are given by that formula.

Basic Operations

Consider two sequences \(a, b\) with ordinary generating functions \(F(x)\) and \(G(x)\), respectively. Then

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

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

Consider multiplication, i.e., 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 Form

When using generating functions, we do not always keep the formal power series form but convert it into a closed form at appropriate times to simplify.

For example, the ordinary generating function of \(\langle 1,1,1,\cdots\rangle\) is \(F(x)=\sum_{n\ge 0}x^n\). We can observe that

\[ F(x)x+1=F(x) \]

Solving this equation yields

\[ F(x)=\frac{1}{1-x} \]

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

Consider the generating function of the geometric sequence \(\langle 1,p,p^2,p^3,p^4,\cdots\rangle\): \(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 geometric sequences are commonly used transformation techniques.

Exercise

Find the ordinary generating functions (both formal power series form and closed form) of the following sequences. 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}\) (where \(m\) is constant, \(n\ge 0\)).
  5. \(a_n=\binom{m+n}{n}\) (where \(m\) is constant, \(n\ge 0\)).
Answer

First:

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

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} \]

Third (using 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} \]

Fourth (binomial theorem):

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

Fifth:

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

This can be proven by induction.

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 as \(a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1)\). Let its ordinary generating function be \(F(x)\). Based on its recurrence relation, we can similarly set up an equation for \(F(x)\):

\[ F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0 \]

Solving yields

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

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

Expansion Method 1

Treat \(x+x^2\) as a single entity. Then we get

\[ \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, we set \(n=k+i+1\) and changed the order of summation. Thus, we obtain the general term formula:

\[ 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 2

Consider solving an equation with undetermined coefficients:

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

Combining the fractions:

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

Equating coefficients of corresponding terms, we get

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

Solving yields

\[ \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 formula for geometric series, we obtain the general term formula for 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 (\(\frac{x}{1-x-x^2}\) is 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 above method. In practice, we often first find the roots of \(Q(x)\), express the denominator in the form \(\prod (1-p_ix)^{d_i}\), and then determine the numerator.

When factoring the denominator yields repeated roots, each repeated root adds an extra partial fraction. For example, consider the generating function

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

To find the general term formula for its coefficients, we set

\[ 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} \]

Then

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

Newton's Binomial Theorem

We redefine the operation for binomial coefficients:

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

Note that \(r\) can be any complex number. In this context, for \(\alpha\in\mathbf{C}\), we have

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

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

Generating Function of Catalan Numbers

Refer to Algebraic derivation of Catalan number forms.

Applications

Next, we present some example problems to illustrate the specific applications of generating functions in OI.

Food

Food

Select \(n\) items from many different types of food, with the following restrictions for each type:

  1. Chengde Burger: even number
  2. Cola: 0 or 1
  3. Chicken Leg: 0, 1, or 2
  4. Peach Soda: odd number
  5. Chicken Nuggets: multiple of 4
  6. Steamed Bun: 0, 1, 2, or 3
  7. Potato Chips with Meat: at most one.
  8. Bread: multiple of 3

Each food type is counted in "units". A scheme is valid as long as the total number of items sums to \(n\). For a given \(n\), compute the number of schemes modulo \(10007\).

This is a classic generating function problem. For one type of food, we can let \(a_n\) denote the number of ways to select \(n\) items of that type and find its generating function. The generating function for selecting a total of \(n\) items from two types of food is the convolution of their generating functions. The generating function for selecting \(n\) items from multiple types is also the convolution of their generating functions.

Understanding that the number of schemes can be represented by convolution, we construct the generating functions (labels correspond to the food types 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 to expanded form (using the fifth exercise from the closed form practice):

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

Thus, the answer is \(\dbinom{n+2}{n-1}=\dbinom{n+2}{3}\).

Sweet

「CEOI2004」Sweet

There are \(n\) piles of candies. Different piles contain different types of candies (i.e., candies in the same pile are of the same type, candies in different piles are of different types). The \(i\)-th pile contains \(m_i\) candies. Now we want to eat at least \(a\) candies but no more than \(b\) candies. Find the number of possible schemes.

Two schemes are considered different if the number of candies eaten differs, or if for some candy type, the number eaten differs between the two schemes.

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

The generating function for the number of ways to eat \(j\) candies from the \(i\)-th pile (obviously 1) is

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

Thus, the generating function for the total number of ways to eat \(i\) candies is

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

Now we need to compute \(\sum_{i=a}^b[x^i]G(x)\).

Since \(n\le 10\), we can brute-force expand \(\prod_{i=1}^n(1-x^{m_i+1})\) (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} \]

We enumerate the coefficient \(c_k\) of the \(x^k\) term in \(\prod_{i=1}^n(1-x^{m_i+1})\). After multiplying with \((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 complexity: \(O(2^n+b)\).

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用