生成函数 | Generating Function

Prerequisites – 前置技能

  1. 高中数列 :等比数列和等差数列的内容,还有一些基本数列变形方法。
  2. 基本的离散数学符号,比如艾弗森括号之类的。
  3. 排列组合的一些公式。

Definition – 定义

我们有一个数列\(\{ f_n \}\),其生成函数就是:

\[ F(x) = \sum_{n = 0}^{\infty} f_n x^n \]

一般的生成函数有很多优美的地方。接下来我会介绍几个比较常用的生成函数的结论或推导。

Example A

先来搞一个简单的:\(f_n = 1\)时。根据等比数列求和公式可以推出:

\[ F(x) = \sum_{n = 0}^{\infty} x^n = \frac{1}{1 – x} \]

Example B

我们现在向 Example A 加上一个系数幂,根据等比数列求和其实也差不多:

\[ F(x) = \sum_{n = 0}^{\infty} a^n x^n = \frac{1}{1 – ax} \]

Example C

这次的系数是二项式系数,其实可以根据二项式定理搞一搞:

\[ F(x) = \sum_{n = 0}^{\infty} {a \choose n} x^n = (1 + x)^a \]

Example D

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注