Bóna · 枚举与解析组合学导论 · 第 3 章 生成函数

3.1　幂级数Power series

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

在本章中，我们将学习到目前为止最先进的计数技巧。我们要学会如何用一个单独的函数——即某个序列的生成函数（generating function）——来编码一个（可能无限长的）序列中的全部元素。通常，我们会先求出一个序列的生成函数，然后再把它解码，也就是说，从生成函数中把序列的各个元素重新计算出来。这一思想是在离散数学中运用连续对象的一个有力范例。让我们先用很短的篇幅复习一下将要用到的那类函数。请放心，本书很快就会回到组合学的讨论上来。

本节目标把后面整章要用的工具——幂级数（power series）——准备好：它是“可以无限长的多项式”。本节要弄清三件事：①什么是幂级数；②如何把组合数 \(\binom{a}{k}\) 推广到任意实数 \(a\)；③实指数的二项式定理 \((1+x)^a=\sum_{n\ge0}\binom{a}{n}x^n\) 以及它的一个最常用特例 \(\dfrac{1}{1-x}=\sum_{n\ge0}x^n\)。

读者无疑是一位好学生，因此读者一定记得微积分里的幂级数。它们很像多项式，也就是说，是变量 \(x\) 的各个幂次乘以常数后求和。但与多项式不同，幂级数可以无限长。例如，\(\displaystyle\sum_{k=0}^{n}x^{k}\) 是一个多项式，而 \(\displaystyle\sum_{k=0}^{\infty}x^{k}\) 是一个幂级数。

多项式（项数有限） 1 + x + x² + ⋯ + xⁿ 到 xⁿ 就停下 幂级数（项数无限） 1 + x + x² + x³ + ⋯ 永远写不完 区别只有一处：项数是“有限”还是“无限”。其余的“幂乘常数再相加”的写法完全一样。
多项式是幂级数的特例：把无限多项里多出来的那些项都取系数 \(0\)，幂级数就退化成多项式。

3.1.1　广义二项式系数

幂级数的一个常见例子是实指数的二项式定理（the binomial theorem with real exponents）。为了复习这条定理，我们首先必须把二项式系数 \(\binom{a}{k}\) 的概念推广到一切实数 \(a\)（这里 \(k\) 仍然必须是一个非负整数）。毕竟，我们不能把 \(\binom{-2.5}{k}\) 定义为集合 \([-2.5]\) 的全部 \(k\) 元子集的个数，因为集合 \([-2.5]\) 根本不存在。

当 \(a\) 不是非负整数时，\(\binom{a}{k}\) 的组合定义无法保留，但它的解析定义（analytic definition）却可以保留。

定义 3.1 设 \(a\) 为任意实数，\(k\) 为非负整数。则定义 \[\binom{a}{k}=\frac{a(a-1)\cdots(a-k+1)}{k!}.\]
为什么这样定义是合理的当 \(a\) 是非负整数时，旧的组合公式 \(\binom{a}{k}=\dfrac{a!}{k!(a-k)!}=\dfrac{a(a-1)\cdots(a-k+1)}{k!}\) 的分子本来就只用到从 \(a\) 往下乘 \(k\) 个连续整数，根本没用到“\(a-k\) 以下”的部分。定义 3.1 只是把这个“只往下乘 \(k\) 个数”的写法原封不动地搬过来——而它对任何实数 \(a\) 都讲得通。

分子 \(a(a-1)\cdots(a-k+1)\) 是从 \(a\) 开始、每次减 \(1\)、一共乘 \(k\) 个因子的乘积。下图把因子的个数数清楚。

a a−1 a−2 ⋯ a−k+1 恰好 k 个因子（再除以 k!）
第 \(1\) 个因子是 \(a\)，第 \(k\) 个因子是 \(a-(k-1)=a-k+1\)，所以一共 \(k\) 个因子。

例如，

\[\binom{1/2}{3}=\frac{\dfrac12\left(\dfrac12-1\right)\left(\dfrac12-2\right)}{3!}=\frac{\dfrac12\cdot\left(-\dfrac12\right)\cdot\left(-\dfrac32\right)}{6}=\frac{3/8}{6}=\frac{3}{48}=\frac{1}{16}.\]
例：逐步算清 \(\binom{1/2}{3}\)
  1. 取 \(a=\tfrac12,\;k=3\)，写出 \(k=3\) 个因子：第一个是 \(\tfrac12\)，第二个是 \(\tfrac12-1=-\tfrac12\)，第三个是 \(\tfrac12-2=-\tfrac32\)。
  2. 分子相乘：\(\dfrac12\cdot\left(-\dfrac12\right)\cdot\left(-\dfrac32\right)\)。先看符号：两个负号相乘为正。再看数值：\(\dfrac{1\cdot1\cdot3}{2\cdot2\cdot2}=\dfrac38\)。所以分子 \(=\dfrac38\)。
  3. 分母是 \(k!=3!=6\)。
  4. 相除：\(\dfrac{3/8}{6}=\dfrac{3}{48}=\dfrac{1}{16}\)。♦
注意结果可以是分数，这正是把 \(a\) 推广成实数后才出现的新现象——当 \(a\) 是非负整数时 \(\binom{a}{k}\) 永远是整数。

现在我们已经准备好从微积分中回忆起实指数的二项式定理了。

定理 3.2 设 \(a\) 为实数，且 \(|x|<1\)。则 \[\tag{3.1}(1+x)^{a}=\sum_{n\ge0}\binom{a}{n}x^{n}=1+\binom{a}{1}x+\binom{a}{2}x^{2}+\cdots.\]
证明. 回忆解析函数 \(f(x)\) 在 \(x=0\) 处的泰勒级数（Taylor series）展开式为 \[f(x)=\sum_{n\ge0}f^{(n)}(0)\,\frac{x^{n}}{n!}.\] 把这一事实用于 \(f(x)=(1+x)^{a}\)。计算 \(f^{(n)}(0)\) 的前几个值，我们看到 \(f^{(0)}(0)=f(0)=1^{a}=1\)，\(f^{(1)}(0)=a\)，\(f^{(2)}(0)=a(a-1)\)，\(f^{(3)}(0)=a(a-1)(a-2)\)，依此类推。由此可以看出规律 \(f^{(n)}(0)=(a)_{n}\)，而这一点用求导法则即可直接用归纳法证明。由于 \((a)_{n}/n!=\binom{a}{n}\)，这就证明了定理。♦

（此处 \((a)_{n}=a(a-1)\cdots(a-n+1)\) 表示从 \(a\) 往下乘的 \(n\) 个因子之积，即定义 3.1 的分子。）

例：把证明里的求导一步步做出来设 \(f(x)=(1+x)^a\)，按链式法则反复求导：
  1. \(f(x)=(1+x)^a\)，代入 \(x=0\)：\(f(0)=1^a=1\)。
  2. \(f'(x)=a(1+x)^{a-1}\)，代入 \(x=0\)：\(f'(0)=a\)。
  3. \(f''(x)=a(a-1)(1+x)^{a-2}\)，代入 \(x=0\)：\(f''(0)=a(a-1)\)。
  4. \(f'''(x)=a(a-1)(a-2)(1+x)^{a-3}\)，代入 \(x=0\)：\(f'''(0)=a(a-1)(a-2)\)。
  5. 每求一次导，前面就多乘一个递减的因子，所以第 \(n\) 阶导在 \(0\) 处的值是 \(f^{(n)}(0)=a(a-1)\cdots(a-n+1)=(a)_n\)。
  6. 代回泰勒公式：第 \(n\) 项系数为 \(\dfrac{f^{(n)}(0)}{n!}=\dfrac{(a)_n}{n!}=\binom{a}{n}\)，于是 \((1+x)^a=\sum_{n\ge0}\binom{a}{n}x^n\)。♦

如果 \(a\) 恰好是一个非负整数，那么对 \(k>a\) 有 \(\binom{a}{k}=0\)，于是 (3.1) 的右边就是有限多个形如 \(c_{i}x^{i}\) 的项之和；换句话说，它是一个多项式。然而，如果 \(a\) 不是正整数，那么右边就是一个形如 \(\sum_{i\ge0}c_{i}x^{i}\) 的无限和，被称为幂级数。

为什么整数指数时会“自动停下”当 \(a\) 是非负整数、取 \(k=a+1\) 时，分子 \(a(a-1)\cdots(a-k+1)\) 一路乘到因子 \(a-k+1=a-(a+1)+1=0\)，于是乘积里出现了因子 \(0\)，整个 \(\binom{a}{k}=0\)。此后所有 \(k>a\) 的项都含这个 \(0\) 因子，全部消失，无限和就缩成有限和——这正是我们熟悉的、初等的二项式定理。
例：取 \(a=2\) 验证它退化成普通二项式定理
  1. \(\binom{2}{0}=1\)，\(\binom{2}{1}=\dfrac{2}{1}=2\)，\(\binom{2}{2}=\dfrac{2\cdot1}{2!}=1\)。
  2. \(\binom{2}{3}=\dfrac{2\cdot1\cdot0}{3!}=0\)（出现因子 \(0\)），此后 \(\binom{2}{k}=0\)。
  3. 于是 (3.1) 给出 \((1+x)^2=1+2x+x^2\)，正是初中学过的完全平方公式。♦

在微积分中，你一定花了许多充满乐趣的时间，去弄清楚某些幂级数对哪些 \(x\) 值收敛（converge）。有些幂级数对所有 \(x\) 值都收敛，例如 \(\sum_{n\ge0}x^{n}/n!\)；另一些则只对一个 \(x\) 值收敛，而且在许多例子中那个值就是零，例如 \(\sum_{n\ge0}n!\,x^{n}\)。你学过各种判别法，比如比值判别法（ratio test）和根值判别法（root test），它们能帮助确定一个给定幂级数对哪些 \(x\) 值收敛。

当一个幂级数对所有 \(x\in[a,b]\) 都收敛时，就有可能把这个幂级数写成一个闭形式（closed form）。例如，读者也许记得，幂级数 \[F(x)=\sum_{n\ge0}x^{n}\] 对 \(x\in(-1,1)\) 收敛，并且在这个区间上， \[\tag{3.2}F(x)=\frac{1}{1-x}.\] 请读者验证：这其实是二项式定理的一个特例——把 (3.1) 中的 \(x\) 换成 \(-x\)，并取 \(a=-1\)。

例：从二项式定理推出 \(\dfrac{1}{1-x}=\sum x^n\)
  1. 在定理 3.2 中取 \(a=-1\)，并把变量 \(x\) 整体替换为 \(-x\)，左边变成 \((1+(-x))^{-1}=(1-x)^{-1}=\dfrac{1}{1-x}\)。
  2. 先算系数 \(\binom{-1}{n}=\dfrac{(-1)(-2)\cdots(-1-n+1)}{n!}=\dfrac{(-1)(-2)\cdots(-n)}{n!}\)。分子是 \(n\) 个负数相乘，符号为 \((-1)^n\)，数值为 \(n!\)，所以 \(\binom{-1}{n}=\dfrac{(-1)^n\,n!}{n!}=(-1)^n\)。
  3. 右边第 \(n\) 项为 \(\binom{-1}{n}(-x)^n=(-1)^n\cdot(-1)^n x^n=(-1)^{2n}x^n=x^n\)（因为 \((-1)^{2n}=1\)）。
  4. 对所有 \(n\) 求和：\(\dfrac{1}{1-x}=\sum_{n\ge0}x^n=1+x+x^2+x^3+\cdots\)，正是 (3.2)。♦
例：用具体数字感受“收敛”与“闭形式”取 \(x=\tfrac12\)（落在 \((-1,1)\) 内）：
  1. 逐项相加：\(1+\tfrac12+\tfrac14+\tfrac18+\tfrac1{16}+\cdots\)，部分和依次为 \(1,\ 1.5,\ 1.75,\ 1.875,\ 1.9375,\dots\)，越来越接近 \(2\)。
  2. 用闭形式 (3.2) 直接算：\(\dfrac{1}{1-\frac12}=\dfrac{1}{1/2}=2\)。两者一致。
  3. 若取 \(x=2\)（落在区间外），各项 \(1,2,4,8,\dots\) 越加越大，级数发散，此时不能用 (3.2)。♦
-1 0 1 收敛区间 (−1, 1)：此处 ∑xⁿ = 1/(1−x) 区间外：发散 区间外：发散
只有当 \(x\) 落在开区间 \((-1,1)\)（两端点空心，表示不含）时，部分和才会稳定地趋于一个有限值 \(\dfrac{1}{1-x}\)。

幂级数将是本章的主要工具。我们会非常喜欢它们，以至于即使它们在任何区间上都不收敛，我们也毫不介意——我们仍然会照样用它们来工作。

承上启下这听起来很奇怪：一个发散的级数还有什么用？关键在于，在组合学里我们把幂级数当作形式对象（即只关心各个系数 \(c_n\)，把 \(x\) 看成一个不必代入数值的“记号”），用它来一次性装下整个序列 \(c_0,c_1,c_2,\dots\)。这就是下一节“生成函数”的核心思想——本节准备的 \(\binom{a}{n}\) 与 \(\dfrac{1}{1-x}=\sum x^n\) 正是后面反复使用的两块零件。

返回 全书目录