高中数学扩展/计数与生成函数

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论与无限过程 — 计数与生成函数 — 离散概率

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

在我们开始之前: 本章假设您已掌握以下知识

1. 有序选择（排列）和无序选择（组合），这些内容在 基本计数 中有所介绍，
2. 部分分数法 以及，
3. 熟练运用 求和符号

一些计数问题

..待续

生成函数

..一些需要补充的动机

要理解本节内容，您需要了解为什么这是真的

$\lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1$

有关上述内容的更详细讨论，请前往 无限与无限过程.

生成函数，也称为形式幂级数，对于解决以下问题很有用

$x_{1}+x_{2}+2x_{3}=m$

其中

$x_{n}\geq 0$; n = 1, 2, 3

如果$m=55$，有多少个不同的解？

在解决这个问题之前，让我们考虑无限多项式

$S=1+x+x^{2}+x^{3}+...+x^{n}+x^{n+1}...$

我们想要得到这个无限多项式的封闭形式。封闭形式只是表达多项式的一种方式，以便它只涉及有限数量的操作。

为了找到封闭形式，我们从我们的函数开始

$S=1+x+x^{2}+x^{3}+...$

我们把函数的两边都乘以x，得到：$xS=x+x^{2}+x^{3}+...$

接下来，我们减去S-xS，得到

S - xS = 1 + x + x^2 + x^3 ... - x - x^2 - x^3 ...

分组类似项，我们得到

(1 - x)S = 1 + (x - x) + (x^2 - x^2) + (x^3 - x^3)

简化为

(1 - x)S = 1

把两边都除以${\frac {1}{1-x}}$，我们得到$S={\frac {1}{1-x}}$

所以的封闭形式是

1 + x + x² + x³ + ...

是

${\frac {1}{1-x}}$

为了方便起见，我们可以写成，虽然这对任何特定的x值都不成立。

$1+x+x^{2}+x^{3}+...={\frac {1}{1-x}}\ ;\ -1<x<1$

信息 - 无限求和

这两个表达式并不相等。只是对于x的某些值（-1 < x < 1），我们可以通过在左侧累加大量项来尽可能接近地逼近右侧。例如，假设x = 1/2，RHS = 2；我们仅使用 5 个项来逼近 LHS，得到 LHS 等于 1 + 1/2 + 1/4 + 1/8 + 1/16 = 1.9375，这接近 2，你可以想象，通过添加越来越多的项，我们将越来越接近 2。

无论如何，我们实际上只关心它的好的代数性质，而不是它的数值。从现在起，我们在写出生成函数时将省略相等成立的条件。

考虑一个更一般的情况

$S=A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...$

其中A和B是常数。

我们可以如下推导出封闭形式

${\begin{matrix}S&=&A+&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\BxS&=&&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\\\(1-Bx)S&=&A\\S&=&{\frac {A}{1-Bx}}\end{matrix}}$

上面推导出的以下恒等式值得花时间和精力去记忆。

$A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...={\frac {A}{1-Bx}}$

练习

1. 求闭合形式

(a)$1-z+z^{2}-z^{3}+z^{4}-z^{5}+...$

(b)$1+2z+4z^{2}+8z^{3}+16z^{4}+32z^{5}+...$

(c)$z+z^{2}+z^{3}+z^{4}+z^{5}+...$

(d)$3-4z+4z^{2}-4z^{3}+4z^{4}-4z^{5}+...$

(e)$1-z^{2}+z^{4}-z^{6}+z^{8}-z^{10}+...$

2. 给定闭合形式，求 xⁿ 系数的函数 f(n)

(a)${\frac {1}{1+z}}$ (提示：注意分母中的加号)

(b)${\frac {1}{1-2z}}$ (提示：将 A=1 和 B=2 代入 ${\frac {A}{1-Bz}}$)

(c)${\frac {z}{1-z}}$ (提示：将 ${\frac {1}{1-z}}$ 中的所有项乘以 z)

代换法

我们知道

1 + z + z² + ... = 1/(1 - z)

通过代换，我们可以得到许多其他生成函数。例如：令 z = x²，我们有

1 + x² + x⁴ + ... = 1/(1 - x²)

同样地

A + ABx + A(Bx)² + ... = A/(1 - Bx)

是通过令 z = Bx 然后将整个表达式乘以 A 获得的。

练习

1. x 的幂的系数是什么

1/(1 - 2x³)

2. x 的幂的系数是什么（提示：提出 1/2）

1/(2 - x)

线性递推关系

斐波那契数列

1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

其中，除前两个数外，每个数都是它前两个数之和。如果一个数的值取决于序列中它前面的数的值，我们称这些数是相关的。斐波那契数列是一个递推关系的例子，它表示为

${\begin{matrix}x_{n}&=&x_{n-1}&+&\ x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

其中，x_n 是序列中的第 (n+ 1) 个数。请注意，序列中的第一个数用 x₀ 表示。给定这个递推关系，我们想问的问题是“我们能否找到序列中第 (n+ 1) 个数的公式？”答案是肯定的，但在我们给出答案之前，让我们来看一些例子。

示例 1

表达式

${\begin{matrix}x_{n}&=&2x_{n-1}&+&3x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\end{matrix}}$

定义一个递推关系。该序列为：1, 1, 5, 13, 41, 121, 365... 求序列中第（n+1）项的公式。

解 设 G(z) 为序列的生成函数，即每个幂的系数（按升序排列）是序列中相应的数字。因此，生成函数看起来像这样

$G(z)=1+z+5z^{2}+13z^{3}+41z^{4}+121z^{5}+...$

现在，通过一系列代数运算，我们可以找到生成函数的闭合形式，并从中得到每个系数的公式

${\begin{matrix}&&G(z)&=&x_{0}+&x_{1}z+&x_{2}z^{2}&+&x_{3}z^{3}+x_{4}z^{4}+x_{5}z^{5}+...\\2z&\times &G(z)&=&&2x_{0}z+&2x_{1}z^{2}&+&...\\3z^{2}&\times &G(z)&=&&&3x_{0}z^{2}&+&...\\\end{matrix}}$

${\begin{matrix}G(z)-2zG(z)-3z^{2}G(z)&=&x_{0}+(x_{1}-2x_{0})z&+\\&&(x_{2}-2x_{1}-3x_{0})z^{2}&+\\&&(x_{3}-2x_{2}-3x_{1})z^{3}&+&...\end{matrix}}$

根据定义 x_n - 2x_{n - 1} - 3x_{n - 2} = 0

${\begin{matrix}(1-2z-3z^{2})&\times &G(z)&=&x_{0}+(x_{1}-2x_{0})z\\\\&&G(z)&=&{\frac {1-z}{1-2z-3z^{2}}}\\\\&&G(z)&=&{\frac {1-z}{(1-3z)(1+z)}}\end{matrix}}$

通过部分分式法，我们得到

$G(z)={\frac {1}{2}}\times {\frac {1}{1-3z}}+{\frac {1}{2}}\times {\frac {1}{1+z}}$

和式中的每一项都具有可识别的闭合形式。我们可以得出结论

$x_{n}={\frac {1}{2}}\times 3^{n}+{\frac {1}{2}}\times (-1)^{n}$

读者可以轻松检查公式的准确性。

示例 2

${\begin{matrix}x_{n}&=&x_{n-1}&+&x_{n-2}&-&x_{n-3};\ {\mbox{for n}}\geq 3\\x_{0}&=&1\\x_{1}&=&1\\x_{2}&=&1\end{matrix}}$

求 x_n 的非递归公式。

解 令 G(z) 为上述序列的生成函数。

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

${\begin{matrix}G(z)(1-z-z^{2}+z^{3})&=&x_{0}&+&(x_{1}-x_{0})z+(x_{2}-x_{1}-x_{0})z^{2}\\G(z)(1-z-z^{2}+z^{3})&=&1-z^{2}\\\\\end{matrix}}$

${\begin{matrix}G(z)&=&{\frac {1-z^{2}}{1-z-z^{2}+z^{3}}}\\\\G(z)&=&{\frac {1-z}{1-2z+z^{2}}}\\\\G(z)&=&{\frac {1}{1-z}}\end{matrix}}$

因此，对于所有 n，x_n = 1。

示例 3

线性递推关系定义为

${\begin{matrix}x_{n}&=&x_{n-1}&+&6x_{n-2}+1;\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

求 x_n 的一般公式。

解 令 G(z) 为递推关系的生成函数。

$G(z)(1-z-6z^{2})=x_{0}+(x_{1}-x_{0})z+(x_{2}-x_{1}-6x_{0})z^{2}+...$

$G(z)(1-z-6z^{2})=1+z^{2}+z^{3}+z^{4}+...$

$G(z)(1-z-6z^{2})=1+z^{2}(1+z+z^{2}+...)$

$G(z)(1-z-6z^{2})=1+{\frac {z^{2}}{1-z}}$

$G(z)(1-z-6z^{2})={\frac {1-z+z^{2}}{1-z}}$

${\begin{matrix}G(z)&=&{\frac {1-z+z^{2}}{(1-z)(1+2z)(1-3z)}}\\G(z)&=&-{\frac {1}{6(1-z)}}+{\frac {7}{15(1+2z)}}+{\frac {7}{10(1-3z)}}\end{matrix}}$

因此

$x_{n}=-{\frac {1}{6}}+{\frac {7}{15}}(-2)^{n}+{\frac {7}{10}}3^{n}$

练习

1. 推导出由以下线性递推关系定义的序列中第（n+1）个数字的公式

${\begin{matrix}x_{n}&=&2x_{n-1}&-&1;\ {\mbox{for n}}\geq 1\\x_{0}&=&1\end{matrix}}$

2. 推导出由以下线性递推关系定义的序列中第（n+1）个数字的公式

${\begin{matrix}3x_{n}&=&-4x_{n-1}&+&x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

3. （可选）推导出第（n+1）个斐波那契数的公式。

进一步计数

考虑以下等式

a + b = n; a, b ≥ 0 为整数

对于固定的正整数 n，有多少个解？我们可以计算解的数量

0 + n = n

1 + (n - 1) = n

2 + (n - 2) = n

...

n + 0 = n

如您所见，有 (n + 1) 个解。解决该问题的另一种方法是考虑生成函数

G(z) = 1 + z + z² + ... + zⁿ

令 H(z) = G(z)G(z)，即

H(z) = (1 + z + z² + ... + zⁿ)²

我断言，H(z) 中 zⁿ 的系数是 a + b = n，a, b > 0 的解的个数。原因在于 *当乘以同类项时，指数会相加*。

考虑

A(z) = 1 + z + z² + z³ + ...

令

B(z) = A²(z)

则

B(z) = (1 + z + z² + z³ + ...) + z(1 + z + z² + z³ + ...) + z²(1 + z + z² + z³ + ...) + z³(1 + z + z² + z³) + ...

B(z) = 1 + 2z + 3z² + ...

现在 zⁿ 的系数（对于 n ≥ 0）显然是 a + b = n (a, b > 0) 的解的个数。

我们现在准备推导出一个非常重要的结果：令 t_k 为 a + b = n (a, b > 0) 的解的个数。那么序列 t_k 的生成函数为

T(z) = (1 + z + z² + ... + zⁿ + ...)(1 + z + z² + ... + zⁿ + ...)

$T(z)={\frac {1}{(1-z)^{2}}}$

即

${\frac {1}{(1-z)^{2}}}=1+2z+3z^{2}+4z^{3}+...+(n+1)z^{n}+...$

计算 a₁ + a₂ + ... + a_m = n 的解

考虑以下等式的解的个数

a₁ + a₂ + ... + a_m = n

其中 a_i ≥ 0; i = 1, 2, ... m。通过应用先前讨论的方法，如果 t_k 是当 n = k 时上述等式的解的个数，则 t_k 的生成函数为

$T(z)={\frac {1}{(1-z)^{m}}}$

但是，t_k 是什么呢？除非您学过微积分，否则很难仅通过观察 T(z) 的方程来推导出公式。在不假设微积分知识的情况下，我们考虑以下计数问题。

“你有三个姐妹，你有 n（n ≥ 3）颗糖果。你决定至少给每个姐妹一颗糖果。有多少种方法可以做到这一点？”

解决这个问题的一种方法是将所有糖果按直线排放在桌子上。由于有 n 颗糖果，因此它们之间有 (n - 1) 个空隙（就像你的每只手有 5 根手指，它们之间有 4 个空隙一样）。现在拿两个分隔物，从可用的 (n - 1) 个空隙中，选择 2 个并把一个分隔物放在你选择的每个空隙中！就这样，你把 n 颗糖果分成三部分，每个姐妹一部分。有 $n-1 \choose 2$ 种方法可以做到这一点！如果你有 4 个姐妹，那么有 $n-1 \choose 3$ 种方法可以做到这一点。如果你有 m 个姐妹，那么有 $n-1 \choose m-1$ 种方法可以做到这一点。

现在考虑：“你有三个姐妹，你有 n 颗糖果。你决定给每个姐妹一些糖果（对给每个姐妹多少颗糖果没有限制）。有多少种方法可以做到这一点？”

请注意，你只是在求解

a₁ + a₂ + a₃ = n

其中 a_i ≥ 0；i = 1, 2, 3。

你可以通过将 n + 3 颗糖果按直线排放在桌子上解决这个问题。拿两个分隔物，从可用的 n + 2 个空隙中选择 2 个空隙。现在你把 n + 3 颗糖果分成了 3 部分，每部分至少有 1 颗糖果。现在从每部分拿回 1 颗糖果，你就可以解决这个问题了！所以解的个数是 $n+2 \choose 2$。更一般地，如果你有 m 个姐妹和 n 颗糖果，那么分享糖果的方法数为

${{n+m-1} \choose {m-1}}={{n+m-1} \choose {n}}$ .

现在得到重要结果，如上所述，方程的解的个数为

a₁ + a₂ + ... + a_m = n

其中 a_i ≥ 0；i = 1, 2, 3 ... m 为

${{n+m-1} \choose {n}}$

即

${\frac {1}{(1-z)^{m}}}=\sum _{i=0}^{\infty }{m+i-1 \choose i}z^{i}$

示例 1

生成函数 T(z) 的封闭形式为

$T(z)={\frac {z}{(1-z)^{2}}}$

以及 T(z) 中 z^k 的系数为 t_k。求 t_k 的显式公式。

解

${\begin{matrix}{\frac {1}{(1-z)^{2}}}&=&\sum _{i=0}^{\infty }(i+1)z^{i}\\\\{\frac {z}{(1-z)^{2}}}&=&z\sum _{i=0}^{\infty }(i+1)z^{i}\\\\&=&\sum _{i=0}^{\infty }(i+1)z^{i+1}\\\end{matrix}}$

因此 t_k = k

示例 2

求解方程的解的个数

a + b + c + d = n

对于所有正整数 n（包括零），并受限制 a, b, c, d ≥ 0。

解 根据公式

${\begin{matrix}{\frac {1}{(1-z)^{4}}}&=&\sum _{i=0}^{\infty }{{n+3} \choose {3}}z^{i}\\\\\end{matrix}}$

所以

解的个数是 ${{n+3} \choose {3}}$

更多计数

我们转向一个稍微难一点的同类问题。假设我们要计算以下方程的解的个数：

2a + 3b + c = n

其中n为整数且$n\geq 0$，且a、b和c大于或等于零。我们可以直接写出封闭形式，我们注意到以下式子的xⁿ项的系数

$(1+x^{2}+x^{4}+...)(1+x^{3}+x^{6}+...)(1+x+x^{2}+...)={\frac {1}{(1-x^{2})(1-x^{3})(1-x)}}$

是所需要的解。这再次归因于，在相乘幂次时，指数相加。

为了获得解的个数，我们用部分分式法将表达式分解成可识别的封闭形式。

示例 1

设s_k是以下方程的解的个数：

2a + 2b = n; a, b ≥ 0

求出s_k的生成函数，然后用n表示出s_n的显式公式。

解

设T(z)为t_k的生成函数

T(z) = (1 + z² + z⁴ + ... + z²ⁿ + ...)²

$T(z)={\frac {1}{(1-z^{2})^{2}}}$

不难看出

$s_{n}=0\ {\mbox{if n is odd}}$

$s_{n}={n/2+1 \choose n/2}={n/2+1 \choose 1}=n/2+1\ {\mbox{if n is even}}$

示例 2

设t_k是以下方程的解的个数：

a + 2b = n; a, b ≥ 0

求出t_k的生成函数，然后用n表示出t_n的显式公式。

解

设T(z)为t_k的生成函数

T(z) = (1 + z + z² + ... + zⁿ + ...)(1 + z² + z⁴ + ... + z²ⁿ + ...)

$T(z)={\frac {1}{(1-z)}}\times {\frac {1}{1-z^{2}}}$

$T(z)={\frac {1}{(1-z)^{2}}}\times {\frac {1}{1+z}}$

$T(z)={\frac {Az+B}{(1-z)^{2}}}+{\frac {C}{1+z}}$

A = -1/4, B = 3/4, C = 1/4

$T(z)=-{\frac {1}{4}}\sum _{i=0}^{\infty }(i+1)z^{i+1}+{\frac {3}{4}}\sum _{i=0}^{\infty }(i+1)z^{i}+{\frac {1}{4}}\sum _{i=0}^{\infty }(-1)^{i}z^{i}$

$t_{k}=-{\frac {1}{4}}k+{\frac {3}{4}}(k+1)+{\frac {1}{4}}(-1)^{k}$

练习

1. 假设

$T(z)={\frac {1}{(1+z)^{2}}}$

是 t_k (k = 0, 1, 2 ...) 的生成函数。求出 t_k 关于 k 的显式公式。

2. 当 m 为给定常数时，以下方程有多少解

$a+b+2c=m$

其中 a，b 和 c ≥ 0

习题集

1. 一家新公司借了 250,000 美元的初始资本。月利率为 3%。公司计划在每个月底前偿还 x 美元。利息在每月最后一天计入债务（按月复利）。

令 D_n 表示 n 个月后剩余的债务。

a) 递归地定义 D_n。

b) 求出 x 的最小值。

c) 求出 D_n 的一般公式。

d) 因此，确定如果 x = 12,000，需要多少个月才能偿还债务。

2. n 的一个划分是一个正整数序列 (λ1,λ1,..,λr)，使得 λ1 ≥ λ2 ≥ .. ≥ λr 且 λ1 + λ2 + .. + λr = n。例如，令 n = 5，则 (5)，(4,1)，(3,2)，(3,1,1)，(2,2,1)，(2,1,1,1)，(1,1,1,1,1) 都是 5 的所有划分。所以我们说 5 的划分数是 7。推导出一个关于一般 n 的划分数的公式。

3. 二叉树是一种树，其中每个节点最多可以有两个子节点。下图是一个二叉树的例子。

a) 令 c_n 表示总共 n 个节点的二叉树的唯一排列数。令 C(z) 为 c_n 的生成函数。

(i) 使用递归定义 C(z)。

(ii) 从而找到 C(z) 的闭合形式。

b) 令 $P(x)={\sqrt {1+ax}}=p_{0}+p_{1}x+p_{2}x^{2}+p_{3}x^{3}...$ 是一个幂级数。

(i) 通过考虑 P(x) 的 n 次导数，找到 p_n 的公式。

(ii) 使用 a) 和 b)(i) 的结果，或其他方法，推导出 c_n 的公式。

提示：与其递归地查找在底部添加节点时 c_n 的变化，不如尝试从相反的方向和方向思考。（而且，不是删除节点）

项目 - 指数生成函数

本项目假设您了解微分。

(可选)0.

(a)

(i) 通过第一原理微分 log x。

(ii)*** 证明最后一部分中无法求值的剩余极限确实收敛。从而通过将该数作为常数来完成微分。

(b) 从而微分 $a^{x}$.

1. 考虑 $E(x)=e^{x}$

(a) 求出 E(x) 的 n 次导数。

(b) 通过考虑 E(x) 在 x = 0 处的 n 次导数的值，将 E(x) 表示为幂级数/无穷多项式形式。

(可选)2.

(a) 求出等比数列（即本章开头介绍的普通生成函数）收敛的条件。（提示：求出部分和）

(b) 因此，证明上一个问题中的 E(x) 在所有实数 x 的值上都收敛。（提示：对于任何固定的 x，一般项的分子是指数函数，而一般项的分母是阶乘。然后呢？）

3. 函数 E(x) 是最基本最重要的指数生成函数，它类似于普通生成函数，但有一些不同，最明显的区别是每一项都带有阶乘分数。

(a) 类似于普通生成函数，E(x) 的多项式展开中的每一项都可以有数字作为系数。现在考虑 $A(x)=a_{1}+a_{2}{\frac {x}{1!}}+a_{3}{\frac {x^{2}}{2!}}+a_{4}{\frac {x^{3}}{3!}}+...$

求 $A'(x)$ 并将其与 A(x) 进行比较。你发现了什么？

(b) 将 nz 代入 E(x)，其中 n 是一个实数，z 是一个自由变量，即 E(nz)。你发现了什么？

4. 除了问题 2 中定义的 A(x) 之外，令 $B(x)=b_{1}+b_{2}{\frac {x}{1!}}+b_{3}{\frac {x^{2}}{2!}}+b_{4}{\frac {x^{3}}{3!}}+...$

(a) A(x) 乘以 B(x) 是多少？将其与普通生成函数进行比较，有什么不同？

(b) 如果我们盲目地将 A(x) 乘以 x（或一般情况下乘以 xⁿ）会怎么样？它会像普通生成函数一样移动系数吗？

注意：带有 *** 的问题是难题，虽然你不一定能回答这些问题，但请随意尝试一下，尽力而为。

反馈

你觉得怎么样？ 太简单还是太难？信息太多还是不够？我们如何改进？请在讨论区留下评论告诉我们。更好的是，自己编辑它，让它变得更好。