生成函数

生成函数 | Generating Functions

定义 | Definition

生成函数是一种数学工具，用于表示一个数列的形式幂级数。它将离散序列转换为形式幂级数，通过操纵生成函数，可以解决数列相关的组合问题。

A generating function is a mathematical tool used to represent a sequence as a formal power series. It transforms a discrete sequence into a formal power series, allowing manipulation of the generating function to solve combinatorial problems related to the sequence.

形式幂级数 | Formal Power Series

对于一个数列 $\{a_n\}$，其生成函数定义为：

For a sequence $\{a_n\}$, its generating function is defined as:

$$G(a_n;x)=\sum _{n=0}^{\infty }{a}_n{x}^n$$

其中，$a_n$ 是数列的第 $n$ 项，$x$ 是形式变量。

where $a_n$ is the $n$-th term of the sequence and $x$ is a formal variable.

常见生成函数类型 | Common Types of Generating Functions

1. 普通生成函数 | Ordinary Generating Function (OGF)

普通生成函数表示数列 $\{a_n\}$ 的形式幂级数：

An ordinary generating function represents the sequence $\{a_n\}$ as a formal power series:

$$A(x)=\sum _{n=0}^{\infty }{a}_n{x}^n$$

示例 | Example

数列 $\{1,1,1,\dots \}$ 的生成函数：

The generating function for the sequence $\{1,1,1,\dots \}$:

$$A(x)=\sum _{n=0}^{\infty }{x}^n=\frac{1}{1-x},|x|<1$$

2. 指数生成函数 | Exponential Generating Function (EGF)

指数生成函数表示数列 $\{a_n\}$ 的形式幂级数，并除以 $n!$：

An exponential generating function represents the sequence $\{a_n\}$ as a formal power series, divided by $n!$:

$$E(x)=\sum _{n=0}^{\infty }{a}_n\frac{x^n}{n!}$$

示例 | Example

数列 $\{1,1,1,\dots \}$ 的指数生成函数：

The exponential generating function for the sequence $\{1,1,1,\dots \}$:

$$E(x)=\sum _{n=0}^{\infty }\frac{x^n}{n!}=e^x$$

3. 二项生成函数 | Binomial Generating Function

二项生成函数是形式幂级数的推广，用于表示二项系数相关的数列：

A binomial generating function is a generalization of a formal power series, used to represent sequences related to binomial coefficients:

$$B(x)=\sum _{n=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)x^n=\frac{1}{(1-x{)}^{k+1}}$$

生成函数的操作 | Operations on Generating Functions

1. 加法 | Addition

如果 $A(x)$ 和 $B(x)$ 是数列 $\{a_n\}$ 和 $\{b_n\}$ 的生成函数，那么 $\{a_n+b_n\}$ 的生成函数为：

If $A(x)$ and $B(x)$ are the generating functions of sequences $\{a_n\}$ and $\{b_n\}$, then the generating function for $\{a_n+b_n\}$ is:

$$A(x)+B(x)$$

2. 乘法 | Multiplication

如果 $A(x)$ 和 $B(x)$ 是数列 $\{a_n\}$ 和 $\{b_n\}$ 的生成函数，那么 $\{c_n\}$ 的生成函数，其中 $c_n={\sum }_{k=0}^n{a}_k{b}_{n-k}$，为：

If $A(x)$ and $B(x)$ are the generating functions of sequences $\{a_n\}$ and $\{b_n\}$, then the generating function for $\{c_n\}$, where $c_n={\sum }_{k=0}^n{a}_k{b}_{n-k}$, is:

$$A(x)\cdot B(x)$$

3. 积分 | Integration

生成函数的积分可以用于求和数列的累积和。数列 $\{a_n\}$ 的生成函数 $A(x)$ 的积分是：

The integration of a generating function can be used to find the cumulative sum of a sequence. The integral of the generating function $A(x)$ for the sequence $\{a_n\}$ is:

$$\int A(x)dx=\sum _{n=0}^{\infty }\frac{a_n{x}^{n+1}}{n+1}+C$$

4. 求导 | Differentiation

生成函数的求导可以用于数列的差分。数列 $\{a_n\}$ 的生成函数 $A(x)$ 的导数是：

The differentiation of a generating function can be used to find the differences of a sequence. The derivative of the generating function $A(x)$ for the sequence $\{a_n\}$ is:

$$A^{\prime }(x)=\sum _{n=1}^{\infty }n{a}_n{x}^{n-1}$$

示例问题 | Example Problem

问题 | Problem

求数列 $\{1,2,3,\dots \}$ 的生成函数。

Find the generating function for the sequence $\{1,2,3,\dots \}$.

解答 | Solution

令 $A(x)$ 为数列 $\{1,2,3,\dots \}$ 的生成函数：

Let $A(x)$ be the generating function for the sequence $\{1,2,3,\dots \}$:

$$A(x)=\sum _{n=1}^{\infty }n{x}^n$$

对 $A(x)$ 求导：

Differentiate $A(x)$:

$$A^{\prime }(x)=\sum _{n=1}^{\infty }n{x}^{n-1}=\frac{1}{(1-x{)}^2}$$

对 $A^{\prime }(x)$ 积分得到 $A(x)$：

Integrate $A^{\prime }(x)$ to get $A(x)$:

$$A(x)=\int \frac{1}{(1-x{)}^2}dx=\frac{x}{(1-x{)}^2}$$

因此，数列 $\{1,2,3,\dots \}$ 的生成函数为：

Therefore, the generating function for the sequence $\{1,2,3,\dots \}$ is:

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

总结 | Summary

生成函数是一个强大的工具，用于表示和操作数列。通过生成函数，可以利用代数方法解决许多组合问题。理解生成函数的基本概念和操作，有助于在数学和计算机科学中进行高级分析和问题解决。

Generating functions are a powerful tool for representing and manipulating sequences. They allow the use of algebraic methods to solve many combinatorial problems. Understanding the basic concepts and operations of generating functions helps in advanced analysis and problem-solving in mathematics and computer science.