Bóna · 枚举与解析组合学导论 · 第 7 章 解析组合学

7.1　指数增长率Exponential growth rates

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

在枚举组合学中常常出现这样的情形：要得到一个精确解答某个问题的公式是困难的、耗时的，甚至是不可能的；而要得到一个把精确解逼近到指定精度的公式却容易得多。在本章中，我们考察这种现象的若干例子，以及在这些情形下可以采用的方法。除非另有说明，本章中所有的幂级数（power series）都假定具有复系数。

正如我们将看到的，证明一个数列大致以某个固定正实数的幂的速度增长，往往相当容易。我们对解析组合学（analytic combinatorics）的探索就从这样的数列开始。

本节目标不去算出数列的精确公式，只问一件事：当 \(n\) 很大时，\(s_n\) 大约像哪个数 \(\alpha\) 的 \(n\) 次幂那样增长？这个 \(\alpha\) 就叫指数增长率。我们将学会：只看一个有理生成函数的分母的最靠近 \(0\) 的根，就能直接读出它系数数列的指数增长率，而无需算出任何一个 \(s_n\)。

7.1.1　有理函数

有理函数（rational functions），即两个多项式之比，是学习我们这套方法的一个良好起点。

7.1.1.1　动机

下面两个数哪个更大：把 \(1000\) 写成若干个等于 \(1\) 或 \(4\) 的部分之有序和（composition，合成）的个数，还是把 \(1000\) 写成若干个等于 \(2\) 或 \(3\) 的部分之有序和的个数？若用 \(a_n\) 记前者的个数、\(b_n\) 记后者的个数，那么用第 3 章的方法容易证明

\[A(x)=\sum_{n\ge 0}a_n x^n=\frac{1}{1-x-x^4},\tag{7.1}\]

以及

\[B(x)=\sum_{n\ge 0}b_n x^n=\frac{1}{1-x^2-x^3}.\tag{7.2}\]

理论上，没有什么能阻止我们去求 \(A(x)\) 与 \(B(x)\) 的部分分式分解（partial fraction decomposition），由此推出 \(a_n\) 与 \(b_n\) 的精确公式，然后比较 \(a_{1000}\) 与 \(b_{1000}\) 的值。然而在实践中，这套流程会极其繁琐。\(A(x)\) 与 \(B(x)\) 的部分分式分解会含有带复数的分式，得到的 \(a_n\) 与 \(b_n\) 的精确公式也不会特别讨喜。而比较 \(n=1000\) 处的值还可能带来另一个麻烦。

于是很自然地要问：能不能用更简单的方式来处理？是否存在一种办法，仅仅通过审视两个数列的生成函数，而不真正算出 \(a_n\) 与 \(b_n\) 的数值，就能判定哪个数列增长得更快？

幸运的是，这个问题的答案是肯定的。本节我们就来发展看清“为何如此、如何做到”的工具。

先把“合成”是什么用数字讲清把 \(5\) 写成若干个等于 \(1\) 或 \(4\) 的部分之有序和，有这些写法：\(1+4,\;4+1,\;1+1+1+1+1\)，共 \(3\) 种，所以 \(a_5=3\)。把 \(5\) 写成若干个等于 \(2\) 或 \(3\) 的部分：\(2+3,\;3+2\)，共 \(2\) 种，所以 \(b_5=2\)。注意“有序”意味着 \(1+4\) 与 \(4+1\) 算作不同。问题问的是 \(n=1000\) 时谁更大——硬算显然不现实，这正是本节方法要解决的。

7.1.1.2　理论背景

下面的定义将是我们刻画一个给定数列增长有多快的关键工具。

定义 7.1 设 \(s_0,s_1,s_2,\dots\) 是一个复数的无穷数列，设 \(\alpha\) 为实数。我们称该数列具有指数增长率（exponential growth rate）\(\alpha\)，如果 换句话说，\(\alpha\) 是使得数列 \(s_1,s_2,\dots\)（或下文中的 \(s_n\)）存在一个无穷子列、其元素绝对值的 \(n\) 次根之极限等于 \(\alpha\) 的最大的那个数。再换一种说法， \[\alpha=\limsup_{n\ge 1}\sqrt[n]{|s_n|}.\]
把定义 7.1 翻译成一句人话“指数增长率 \(\alpha\)”就是：当 \(n\) 很大时，\(|s_n|\) 的大小大致是 \(\alpha^n\) 这个量级。检验办法是开 \(n\) 次方：算 \(\sqrt[n]{|s_n|}\)，看它趋向哪个数。之所以用 \(\limsup\)（上极限）而不用普通极限，是因为有的数列会“忽大忽小”（比如有些项是 \(0\)），普通极限可能不存在；上极限取的是“所有子列能达到的最高的那个极限值”。
例 7.2 设 \(s_n=n\cdot 2^n\)。则数列 \(s_n\) 的指数增长率为 \(2\)。
解：这是因为 \(\sqrt[n]{s_n}=2\cdot\sqrt[n]{n}\to 2\)。♦
例 7.3 设 \(s_n=2^n/n^{100}\)。则数列 \(s_n\) 的指数增长率为 \(2\)。
解：这是因为 \(\sqrt[n]{s_n}=2/\sqrt[n]{n^{100}}\to 2\)。♦
为什么开 \(n\) 次方后多项式因子“消失”
  1. 例 7.2 里多了一个因子 \(n\)，例 7.3 里除了一个因子 \(n^{100}\)，但两者的增长率都还是 \(2\)。
  2. 关键事实：对任意非零多项式 \(p(n)\)，都有 \(\displaystyle\lim_{n\to\infty}\sqrt[n]{|p(n)|}=1\)。例如 \(\sqrt[n]{n}\to 1\)，\(\sqrt[n]{n^{100}}=(\sqrt[n]{n})^{100}\to 1^{100}=1\)。
  3. 所以把一个数列乘以或除以任何非零多项式，都不会改变它的指数增长率——多项式因子比指数因子小得多。
  4. 由此还得到：若 \(f_n=p(n)\) 本身就是某个非零多项式，则数列 \(f_n\) 的指数“阶”（exponential order）为 \(1\)。
例 7.4 设 \(s_n=3^n+(-3)^n\)。则数列 \(s_n\) 的指数增长率为 \(3\)。

注意在上一个例子中，每隔一项就有一项是 \(0\)（当 \(n\) 为奇数时 \(3^n+(-3)^n=3^n-3^n=0\)），但这并不影响数列的指数增长率。决定整个数列增长率的，是其中具有最高增长率的那个无穷子列。在本例中，那就是子列 \(r_n=s_{2n}\)（偶数下标项 \(s_{2n}=2\cdot 3^{2n}\)）。

大 n=123456 偶项 = 2·3ⁿ 越来越大 奇项 = 0
奇数项全为 \(0\)（蓝点贴在轴上），偶数项 \(2\cdot 3^{2n}\) 飞速增大（红点）。增长率由“最高的子列”——偶数项——决定，故为 \(3\)。

不言而喻，并非所有数列都有有限的增长率。回忆记号 \(f(x)\sim g(x)\) 表示 \(\displaystyle\lim_{x\to\infty}f(x)/g(x)=1\)。由于数列是定义域为自然数集的函数，这个定义对数列同样有意义。

例 7.5 设 \(a_n=n!\)。则数列 \(a_n\) 具有无穷大的增长率。
解：这可由斯特林公式（Stirling's formula）证明，该公式断言 \(n!\sim (n/e)^n\sqrt{2\pi n}\)，于是 \(\sqrt[n]{a_n}\sim n/e\)，它显然发散到无穷。我们最早在 (1.13) 中提到过这个公式。另一种办法是利用 \(a_{n+1}/a_n=n+1\)，它同样发散到无穷。♦

这并不是说，如果一个数列的元素满足 \(a_n\ge n!\)，我们就无法对它提出涉及指数增长率的有趣问题。例如，我们可以问这个数列比阶乘数列快多少，即问数列 \(a_n/n!\) 的指数增长率。在能够算出数列 \(a_n\) 的指数型生成函数（exponential generating function）的情形里，这个问题尤其合适。

请读者在补充习题 2 中证明下面两个命题。

命题 7.6 设数列 \(f_n\) 具有指数增长率 \(a\)，数列 \(g_n\) 具有指数增长率 \(b\)，并假设两个数列都由复数构成。假设 \(a>b\)。则数列 \(f_n+g_n\) 具有指数增长率 \(a\)。

注意，去掉 \(a>b\) 这个条件，命题 7.6 就不成立。一个反例是 \(f_n=(-2)^n\) 与 \(g_n=(-2)^{n+1}\)。尽管如此，下面这条较弱的陈述总是成立。

为什么需要 \(a>b\)（看反例）取 \(f_n=(-2)^n\)、\(g_n=(-2)^{n+1}=-2\cdot(-2)^n\)，两者增长率都是 \(2\)（即 \(a=b=2\)，不满足 \(a>b\)）。此时 \(f_n+g_n=(-2)^n\big(1+(-2)\big)=-(-2)^n\)。命题 7.6 之所以要求 \(a>b\)：当两个增长率相等时，求和过程中可能发生相消，从而使和的增长率低于 \(a\)（最极端的情形如 \(g_n=-f_n\)，此时 \(f_n+g_n\equiv 0\)）；只有在 \(a>b\) 时，较大的那一项无法被另一项抵消，才能保证和的增长率恰好等于 \(a\)。
命题 7.7 设数列 \(f_n\) 具有指数增长率 \(a\)，数列 \(g_n\) 具有指数增长率 \(b\)，并假设两个数列都由复数构成。假设 \(a\ge b\)。则 \(f_n+g_n\) 的指数增长率至多为 \(a\)。
证明. 反设结论不成立，即数列 \(f_n+g_n\) 存在一个无穷子列 \(s_i\)（其中 \(i\in I\)，\(I\) 为某个无穷的正整数集合），满足不等式 \(\displaystyle\lim_{i\to\infty}\sqrt[i]{s_i}=a'>a\)。
考虑无穷子列 \(s_i=f_i+g_i\)。令 \(I_1\subseteq I\) 为满足 \(|f_i|\ge|g_i|\) 的那些下标构成的集合，令 \(I_2\subseteq I\) 为满足 \(|f_i|<|g_i|\) 的那些下标构成的集合。由于 \(I\) 是无穷的，所以 \(I_1\) 与 \(I_2\) 中至少有一个是无穷的。不妨假设 \(I_1\) 是无穷的。
现在注意，若 \(i\in I_1\)，则 \[|s_i|=|f_i+g_i|\le|f_i|+|g_i|\le 2|f_i|,\] 这意味着数列 \(f_i\)（\(i\in I_1\)）的指数阶至少为 \(a'\)，与我们的假设（\(f_n\) 增长率为 \(a♦
命题 7.7 证明的逻辑骨架
  1. 用反证法：假设和数列居然冒出了一个增长率 \(a'>a\) 的无穷子列。
  2. 把这个子列的下标按“\(f\) 占优”还是“\(g\) 占优”分成两堆 \(I_1,I_2\)；无穷个下标分进两堆，至少有一堆是无穷的。
  3. 取占优的那一堆（设为 \(I_1\)）：那里 \(|f_i|\ge|g_i|\)，所以三角不等式给出 \(|s_i|\le 2|f_i|\)。
  4. 开 \(i\) 次方：\(\sqrt[i]{|f_i|}\ge \sqrt[i]{|s_i|/2}\to a'\)（因子 \(2\) 开 \(i\) 次方趋于 \(1\)），于是 \(f\) 也有了 \(\ge a'\) 的子列，超过它自己的增长率 \(a\)，矛盾。

现在我们开始把一个数列的增长率放进生成函数的语境中。注意，除非另有说明，本节中所有幂级数都取自复数域，即它们具有复系数。我们只假定读者熟悉复数 \(z\) 的两种写法：笛卡儿写法 \(z=x+iy\)（其中 \(x,y\) 为实数），以及极坐标写法 \(z=re^{i\varphi}\)（其中 \(r\) 为非负实数，\(\varphi\) 称为 \(z\) 的辐角（argument），是以弧度计的角）。读者大概也熟悉基本的复数运算，即知道如何对复数做加、减、乘、除，如何求其幂，以及如何计算其绝对值。我们还假定读者熟悉欧拉公式（Euler's formula）：

\[e^{i\varphi}=\cos\varphi+i\sin\varphi\tag{7.3}\]

对一切实数 \(\varphi\) 成立。

回忆：有理函数是两个多项式之比。

定义 7.8 设 \(F(x)=P(x)/Q(x)\) 为一个有理函数，使得 \(P(x)\) 与 \(Q(x)\) 没有任何公共根。则称复数 \(x_0\) 是 \(F(x)\) 的一个奇点（singular point），如果 \(Q(x_0)=0\)。
例 7.9 有理函数 \[F(x)=\frac{x^2+3x+2}{(x-1)^2(x^2+1)}\] 的奇点为 \(x_0=1\)、\(x_0=i\) 和 \(x_0=-i\)。
验算例 7.9 的奇点
  1. 先看分子分母有没有公共根：分子 \(x^2+3x+2=(x+1)(x+2)\)，根为 \(-1,-2\)；分母的根为 \(1,i,-i\)。没有重叠，符合定义 7.8 的前提。
  2. 奇点就是分母的根。\((x-1)^2=0\) 给出 \(x=1\)；\(x^2+1=0\) 给出 \(x=\pm i\)。
  3. 所以奇点是 \(1,\;i,\;-i\)，共三个（\(x=1\) 是二重根但作为奇点只算一个点）。

写成最简形式的有理函数，其奇点正是分母的根。即便如此，引入“奇点”这个名字仍是值得的，因为它对那些并非有理函数的函数也会有意义。

若 \(r_1\) 是多项式 \(Q(x)\) 的一个根，我们称 \(r_1\) 是 \(Q(x)\) 的一个最小模根（root of smallest modulus），如果不存在 \(Q(x)\) 的根 \(r_2\) 满足 \(|r_1|>|r_2|\)。

“最小模根”是什么每个根 \(r\) 是一个复数，它的“模”\(|r|\) 就是它到原点 \(0\) 的距离。最小模根就是离 \(0\) 最近的那个根。下面的定理告诉我们：这个离 \(0\) 最近的根，单凭它的位置就能定出整条系数数列的增长速度。

下面的定理给出了一种求有理函数系数数列指数增长率的简便方法。

定理 7.10 设 \[S(x)=\sum_{n\ge 0}s_n x^n=\frac{P(x)}{Q(x)}\] 为一个有理函数，其中 \(Q(0)\ne 0\)，并假设 \(P(x)\) 与 \(Q(x)\) 没有任何公共根，还假设 \(Q(x)\) 有唯一的最小模根 \(r_1\)。则系数数列 \(s_n\) 的指数增长率等于 \(|z_1|\)，其中 \(z_1=1/r_1\)。

注意，即使去掉“\(Q(x)\) 有唯一最小模根”这一假设，定理依然成立，只是用我们现有的工具去证明它会稍显繁琐。我们将在下一节证明那个版本的定理。

证明. 不妨假设 \(Q(x)\) 的常数项为 \(1\)。事实上，把一个幂级数除以一个常数，并不改变其系数的指数增长率。
现在令 \(Q(x)=(1-z_1x)^{d_1}(1-z_2x)^{d_2}\cdots(1-z_kx)^{d_k}\)。换句话说，令 \(d_i\) 为 \(r_i\) 作为 \(Q(x)\) 之根的重数。注意这个等式等价于 \(Q(x)=C(r_1-x)^{d_1}(r_2-x)^{d_2}\cdots(r_k-x)^{d_k}\)。
我们可以假设 \(Q(x)\) 的次数大于 \(P(x)\) 的次数。请读者在习题 1 中证明这一简单事实。
于是，正如读者在微积分中见过的那样，\(S(x)=P(x)/Q(x)\) 具有如下形式的部分分式分解： \[\begin{aligned} S(x)=\;&\frac{C_{1,1}}{1-z_1x}+\frac{C_{1,2}}{(1-z_1x)^2}+\dots+\frac{C_{1,d_1}}{(1-z_1x)^{d_1}}\tag{7.4}\\ +\;&\frac{C_{2,1}}{1-z_2x}+\frac{C_{2,2}}{(1-z_2x)^2}+\dots+\frac{C_{2,d_2}}{(1-z_2x)^{d_2}}+\dots\tag{7.5}\\ +\;&\frac{C_{k,1}}{1-z_kx}+\frac{C_{k,2}}{(1-z_kx)^2}+\dots+\frac{C_{k,d_k}}{(1-z_kx)^{d_k}},\tag{7.6} \end{aligned}\] 其中 \(C_{i,j}\) 都是常数。
事实上，把两边同乘 \(Q(x)\)，便得到一个关于两个多项式的等式，其中一个显然就是多项式 \(P(x)\)。对所有 \(n\) 令 \(x^n\) 的系数相等，就可以确定每个 \(C_{i,j}\) 的值。
于是 \(S(x)\) 是若干幂级数之和，每一个都形如 \(C_{i,j}/(1-z_ix)^j\)。这些被加项中，哪一个的系数数列具有最高的指数增长率？由二项式定理的一般形式（定理 3.2）我们知道 \[\frac{1}{(1-z_ix)^j}=(1-z_ix)^{-j}=\sum_{n\ge 0}\binom{j+n-1}{j-1}z_i^n x^n.\] 由于 \(\binom{j+n-1}{j-1}\) 只是关于 \(n\) 的一个 \(j-1\) 次多项式，可知此类幂级数的指数增长率为 \(|z_i|\)，对任意 \(j\) 皆然。
因此，数列 \(s_n\)（即 \(S(x)\) 的系数数列）是若干个我们已知其指数增长率 \(|z_i|\) 的数列之和，即 \[s_n=\sum_{i=1}^{k}\sum_{j=1}^{d_i}C_{i,j}\,z_i^n\binom{j+n-1}{j-1}.\]
回忆 \(r_1\) 是 \(Q(x)\) 唯一的最小模根，故对任意 \(i\ne 1\) 有 \(|z_1|>|z_i|\)（因为 \(z_i=1/r_i\)，\(r_1\) 最小则 \(z_1\) 最大）。因此，所有不含 \(z_1\) 的那些数列（即 \(i\ne 1\) 的项）之和 \(g_n\)，由命题 7.7，其指数增长率小于 \(|z_1|\)。另一方面，含 \(z_1\) 的那些数列之和 \(f_n\) 具有指数阶 \(|z_1|\)，因为它正好等于 \(z_1^n\) 乘以一个非零多项式。于是由命题 7.6，结论成立。♦
把定理 7.10 的证明压成五步
  1. 规范化：把分母 \(Q(x)\) 调成常数项为 \(1\)，不影响增长率。
  2. 因式分解：\(Q(x)=\prod_i(1-z_ix)^{d_i}\)，每个 \(z_i=1/r_i\)。最小模根 \(r_1\) 对应最大的 \(|z_1|\)。
  3. 部分分式：把 \(S(x)\) 拆成一堆 \(C_{i,j}/(1-z_ix)^j\) 之和。
  4. 逐块读增长率：每一块展开成幂级数后，系数 \(=\binom{j+n-1}{j-1}z_i^n\)，多项式因子开 \(n\) 次方趋于 \(1\)，所以这块的增长率就是 \(|z_i|\)。
  5. 取最大者：含 \(z_1\) 的块增长率为 \(|z_1|\)（最大），其余块更小；由命题 7.6 / 7.7，整体增长率 \(=|z_1|=1/|r_1|\)。
实轴 虚轴 0 r₁ 最小模根 r₂ r₃ r₄ 绿色虚线圆半径 = |r₁|（离 0 最近）
分母的所有根散布在复平面上；离原点最近的那个 \(r_1\) 决定一切。增长率 \(=1/|r_1|\)：\(r_1\) 越靠近 \(0\)，数列增长越快。

现在是时候回到 7.1.1.1 节开头提到的那个组合例子了。那个问题是要判定 \(A(x)=1/(1-x-x^4)\) 的系数与 \(B(x)=1/(1-x^2-x^3)\) 的系数哪个增长得更快。定理 7.10 告诉我们，要找出这些增长率，就得求出两个分母的最小模根。借助我们惯用的软件包可知：对 \(A(x)\)，那个根约为 \(r_1=0.7245\)；而对 \(B(x)\)，约为 \(r_1=0.7549\)。因此数列 \(a_n\) 的指数增长率等于 \(z_1=1/0.7245=1.3803\)，而数列 \(b_n\) 的指数增长率为 \(z_1=1/0.7549=1.3247\)，所以数列 \(a_n\) 增长得更快。

回答开篇之问分母 \(1-x-x^4\) 离 \(0\) 最近的根 \(\approx 0.7245\)，取倒数得增长率 \(1.3803\)；分母 \(1-x^2-x^3\) 的最近根 \(\approx 0.7549\)，倒数得 \(1.3247\)。\(1.3803>1.3247\)，所以“部分为 \(1\) 或 \(4\)”的合成数 \(a_n\) 增长更快。我们没有算出任何一个 \(a_{1000}\) 或 \(b_{1000}\)，只比了两个根的大小——这正是本节方法的威力。

让我们再考察几个求“由组合方式定义的数列”之指数增长率的例子。

例 7.11 设 \(h_n\) 为字母表 \(\{A,B,C\}\) 上长度为 \(n\)、且不含连续子词 \(ABC\) 的单词个数。求数列 \(h_n\) 的指数增长率。
解：若取一个被 \(h_n\) 计数的单词 \(w\) 并在其末尾添一个字母，得到的一般是被 \(h_{n+1}\) 计数的单词；唯一的例外是当 \(w\) 以 \(AB\) 结尾、且我们添到末尾的字母是 \(C\) 时。由此导出递推关系 \[h_{n+1}=3h_n-h_{n-2}\] 对 \(n\ge 2\) 成立，而 \(h_0=1,\;h_1=3,\;h_2=9\)。令 \(H(x)=\sum_{n\ge 0}h_n x^n\)，上面展示的递推关系导出函数方程 \[H(x)-9x^2-3x-1=3x\big(H(x)-3x-1\big)-x^3H(x),\] \[H(x)=\frac{1}{1-3x+x^3}.\] 正如任何数学软件包都会告诉我们的，\(H(x)\) 分母的最小模根在 \(x_1=0.3473\)，故数列 \(h_n\) 的指数增长率为 \(1/0.3473=2.8794\)。♦
例 7.11 的递推为何长这样
  1. 一个合法（不含 \(ABC\)）的长度 \(n\) 单词，末尾添一个字母，候选有 \(3\) 种（\(A/B/C\)），故先写 \(3h_n\)。
  2. 但有一类会“添出” \(ABC\)：原词以 \(AB\) 结尾、又添了 \(C\)。这类原词其实是“前面任意合法、再接 \(AB\)”，数量恰为 \(h_{n-2}\)（前 \(n-2\) 位合法，末两位固定为 \(AB\)）。
  3. 把这些非法情况减掉：\(h_{n+1}=3h_n-h_{n-2}\)。
  4. 结果 \(2.8794\) 略低于 \(3\)，与直觉相符：因为 \(3\) 元字母表上全部长度 \(n\) 单词共 \(3^n\) 个，其增长率正是 \(3\)；加了“禁止 \(ABC\)”这个限制，增长率被压低了一点点。

于是数列 \(h_n\) 的指数增长率略低于 \(3\)，这印证了我们的直觉，因为 \(3\) 元字母表上所有长度为 \(n\) 的单词的个数其指数增长率为 \(3\)。

这里正好提一句：在本章其余部分，对于次数大于 \(2\) 的多项式，我们将经常需要求多项式 \(p(x)\) 中最靠近 \(0\) 的那个根。在这类情形下，我们将直接从软件包中获取该根。

例 7.12 我们抛一枚均匀硬币 \(n\) 次。设 \(a_n\) 为不含连续四个正面的可能结果序列的个数。求数列 \(a_n\) 的指数阶。
解：我们使用定理 3.25。先考虑那些至少含一个反面的可接受结果序列。每个这样的序列可以拆成三段：最后一个反面之前的那段、最后这个反面本身、以及最后这个反面之后的部分——后者必须全是正面，且长度至多为三。
若一个可接受结果序列不含任何反面，则它的长度至多为三，且每个这样的长度恰有一个这样的序列。由定理 3.25，这导出函数方程 \[A(x)=A(x)\cdot x\cdot(1+x+x^2+x^3)+1+x+x^2+x^3,\] \[A(x)=\frac{x^3+x^2+x+1}{1-x-x^2-x^3-x^4}.\] 分母的最小模根为 \(0.5188\)，故数列 \(a_n\) 的系数的指数增长率为 \(1/0.5188\approx 1.9276\)。♦
最后反面之前（任意合法） 反面 T 之后全是正面 H 长度 0,1,2 或 3 尾部最多 3 个 H，才能保证不出现连续 4 个 H
把含反面的合法序列按“最后一个反面”切成三段。尾段最多 \(3\) 个正面（对应 \(1+x+x^2+x^3\)），这正是函数方程的来源。

我们指出 \(\displaystyle\lim_{n\to\infty}1.9276^n/2^n=0\)，所以一个长度为 \(n\) 的均匀抛硬币序列含有连续四个正面的概率，当 \(n\) 趋于无穷时收敛到 \(1\)。不含连续四个正面的序列个数的指数增长率小于 \(2\)（无限制抛硬币序列的指数增长率），但相差不大。我们邀请读者解释：如果改为计数不含连续 \(k\) 个正面的序列，会发生什么。

返回 全书目录