「BUAA Discrete Mathematics Chapter7」递推关系和生成函数

Part 0

Part 1 生成函数

为什么研究生成函数

生成函数也叫母函数，研究生成函数是因为其适合求解计数问题。

一方面，我们将生成函数看作代数对象，用代数手段计算一个问题的可能性的数目；另一方面，生成函数是无限可微分函数的泰勒级数。因此，如果找到这样的函数和它的泰勒级数，那么泰勒级数的系数就给出了问题的解。值得注意的是，我们讨论收敛的级数并且只在形式上操作幂函数。

生成函数定义

设

$$h_0,h_1,h_2, \cdots , h_n , \cdots$$

是无穷数列，定义这个数列的生成函数为无穷级数：

$$g(x) = h_0+h_1x+h_2x^2+ \cdots +h_nx^n+\cdots$$

即，生成函数的 $ x ^ n $ 的系数是数列第 $ n $ 项（从 $ 0 $ 开始） $ h_n $ 。我们可以将 $ x ^ n $视作占位符。

对于有限数列：

$$h_0,h_1,h_2,\cdots,h_m$$

可以看成无穷数列：

$$h_0,h_1,h_2,\cdots,h_m,0,0,\cdots$$

因而也可以得到对应的生成函数：

$$g(x) = h_0+h_1x+h_2x^2+ \cdots +h_mx^m$$

多重集的组合与排列

设集合 $ S $ 包含重数分别为 $ n_1, n_2, \cdots n_t $ 的 $ t $ 类元素，

• $ S $ 的 $ r $ 组合（当 $ \forall n_i \ge r(i = 1,2,\cdots ,t) $ 时）的个数为：

  $$\tbinom{r + t - 1}{r}$$
  • 如果存在一个 $ n_i < r $ ：容斥原理
  • 或者也可以对每类元素的出现个数进行约束：采用我们本章的生成函数

• $ S $ 的排列的个数： $ \frac{n!}{n_1!n_2!\cdots n_t!} $

  • 或者也可以对每类元素的出现个数进行约束：采用我们本章的指数生成函数

常见展开式

• $$(1+x)^n = \sum_{k = 0}^{n} \tbinom{n}{k}x^k$$
• $$(1-x)^n = \sum_{k = 0}^{n}(-1)^k\tbinom{n}{k}x^k$$

对满足 $ |x| < 1 $ 的任意 $ x $ ，有：

• $$\frac{1}{(1+x)^n} = \sum_{k=0}^{\infty}(-1)^k\tbinom{n + k - 1}{k}x^k$$
• $$\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty}\tbinom{n + k - 1}{k}x^k$$

$ n = 1 $ 时，得：

• $$\frac{1}{(1+x)} = \sum_{k=0}^{\infty}(-1)^kx^k \quad (|x|<1)$$
• $$\frac{1}{(1-x)} = \sum_{k=0}^{\infty}x^k \quad (|x| < 1)$$

令 $ x = y ^ m $ ，得：

• $$\frac{1}{(1+y^m)} = \sum_{k=0}^{\infty}(-1)^k{y^m}^k \quad (|y|<1)$$
• $$\frac{1}{(1-y^m)} = \sum_{k=0}^{\infty}{y^m}^k \quad (|y|<1)$$

---

生成函数的应用

利用生成函数求解多重集的组合个数

思路：对于给定的有限制的多重集问题，其可以被表述为：

$$e_1 + e_2 + \cdots + e_k = n$$

其中，对每个因子 $ e_i $ 的限制可以被体现在其生成函数中，表现如下：

$$g(x) = (\sum^{e_1}{x^{e_1}}) \times (\sum^{e_2}{x^{e_2}}) \times \cdots \times (\sum^{e_k}{x^{e_k}})$$

对于 $ \sum^{e_i}{x^{e_i}} $ ，可以通过上述常见展开式化为一个有理式，如 $ \frac{1}{(1-x)^2}$ ，将 $ k $ 个有理式的乘积化简得到的有理式可以再推出第k项的系数，即为 $ h_k $ 的系数。

特别地，如果 $ e_i $ 前有系数，如 $ 2e_1 $ ，进行变量替换，并给新变量加上倍数限制即可。

---

排列逆序与定理7.2.1

排列逆序

对于集合 $ {1,2, \cdots ,n } $的排列 $ \pi = i_1,i_2,\cdots i_n$ 中的逆序指的是 $ k < l $ 且 $ i_k > i_l $ 的有序数对 $ (i_k, i_l) $ 。这样的逆序数我们记作 $ inv (\pi) $ 。

设 $ h(n, t) $ 表示 $ { 1,2,\cdots ,n } $ 的排列中有 $ t $ 个逆序的排列的个数

定理7.2.1

数列 $ h(n,0),h(n,1),h(n,2),\cdots h(n,n(n-1)/2) $ 的生成函数为：

$$g(x) = h(n,0)+h(n,1)x+h(n,2)x^2 +\cdots + h(n,n(n-1)/2)x^{n(n-1)/2} = \frac{\prod_{j=1}^{n}{1-x^j}}{(1-x)^n}$$

---

Part 2 指数生成函数

为什么需要指数生成函数

在Part 1 生成函数中，我们介绍了利用 $ {1,x,x^2,\cdots ,x^k,\cdots} $ 获得生成函数的方法，并解决了一些计数数列问题，如多重集的组合问题。

而在多重集的排列问题中，更有效的办法是考虑通过 $ { 1,x,\frac{x^2}{2!},\cdots \frac{x^n}{n!} , \cdots } $ 获得指数生成函数。

指数生成函数定义

对于给定数列：

$$h_0,h_1,h_2, \cdots , h_n , \cdots$$

其指数生成函数定义为：

$$g^{(e)}(x) = \sum_{n=0}^{\infty}h_n\frac{x^n}{n!} = h_0+h_1x+h_2\frac{x^2}{2!}+\cdots+h_n\frac{x^n}{n!}+\cdots$$

定理7.3.1

对于有 $ k $ 种不同类型的对象且每种对象都有有限重数的多重集合 $ S $ ，下述定理给出其 $ n $ 排列数的指数生成函数：

设 $ S $ 是多重集合 $ { n_1 \cdot a_1,n_2 \cdot a_2, \cdots , n_k \cdot a_k } $ ， 其中 $ n_1, n_2, \cdots , n_k $ 是非负整数，设 $ h_n $ 是 $ S $ 的 $ n $ 排列数，则数列 $ h_0, h_1, h_2, \cdots h_n , \cdots $ 的指数生成函数 $ g^{(e)}(x) $ 由下式给出：

$$g^{(e)}(x) = f_{n_1}(x)f_{n_2}(x)\cdots f_{n_k}(x)$$

其中，对于 $ i = 1,2,\cdots,k $ ，有：

$$f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^{n_i}}{ {n_i}!}$$

值得注意的是，上式也可以推广到无穷重数，即存在 $ n_i $ 为 $ \infty $。

常用展开式

• $$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!} + \cdots$$
• $$e ^ {-x} = \sum _{n = 0} ^{\infty} (-1)^{n} \frac{x^n}{n!} = 1 - x + \frac{x^2}{2!} + \cdots + (-1)^n \frac{x^n}{n!} + \cdots$$
• $$\frac{1}{2} (e^x + e^{-x}) = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots + \frac{x^{2n}}{(2n)!} + \cdots$$
• $$\frac{1}{2}(e^{x} - e^{-x}) = x + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots + \frac{x^{2n+1}}{(2n+1)!} + \cdots$$

Part 3 线性齐次递推关系

给定下述 $ k $ 阶线性递推关系：

$$h_n = a_1 h_{n - 1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k} + b_n \quad (n \ge k)$$

当 $ b_n = 0 $ 时，为线性齐次递推关系；如果 $ a_i $ 为常数，则为常系数线性递推关系。

我们在这里研究的主要是 $ k $ 阶常系数线性齐次递推关系。

定理7.4.1

设 $ q $ 是一个非零的数。 $ h_n = q^n $ 是下面常系数线性齐次递推关系

$$h_n - a_1h_{n - 1} - a_2 h_{n - 2} - \cdots - a_k h_{n - k} = 0 \quad (a_k \ne 0, n \ge k)$$

的解，当且仅当 $ q $ 是下面多项式方程

$$x^k - a_1 x^{k - 1} - a_2 x^{k - 2} - \cdots - a_k = 0$$

的根。如果多项式方程有 $ k $ 个不同的根 $ q_1, q_2, \cdots , q_k $ ，则

$$h_n = c_1 q_1^{n} + c_2 q_2^{n} + \cdots + c_k q_k^{n}$$

在下述意义之下是原常系数线性齐次递推关系的通解：无论给定怎样的初始值 $ h0, h_1, \cdots , h{k - 1} $ ，均存在常数 $ c_1, c_2, \cdots c_k $ 使得 $ h_n $ 通项是满足递推关系和初始值的唯一解。

特征方程法

定理7.4.1中给出的多项式方程即为特征方程， $ q $ 即为特征根，因此特征方程法解题步骤归纳如下：

• 列出特征方程
• 求出特征根 $ { q_1, q_2, \cdots , q_k } $ （一元多次方程组，因式分解.etc）
• 利用初始值求通解 $ { c_1, c_2, \cdots , c_k} $ （多元一次方程组，线性代数问题）

值得注意的是，上面的解法中我们要求了 $ q_i $ 彼此不同，但是如果不满足这一条件，即，出现了重根，可以参考《组合数学》P236的解决办法。更一般而言，我们给出定理7.4.2：

定理7.4.2

设 $ q_1, q_2, \cdots , q_t $ 是常系数线性齐次递推关系

$$h_n = a_1 h_{n - 1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k} \quad , a_k \ne 0 \quad (n \ge k)$$

的特征方程互不相同的根。如果 $ q_i $ 是特征方程的 $ s_i $ 重根，那么这个递推关系的通解中对应 $ q_i $ 的部分是

$$H_n^{(i)} = c_1 q_i^n + c_2nq_i^n + \cdots + c_{s_i}n^{s_i - 1}q_i^n = (c_1 + c_2n + \cdots + c_{s_i}n^{s_i - 1})q_i^n$$

这个递推关系的通解是：

$$h_n = H_n^{(1)} + H_n^{(2)} + \cdots + H_n^{(t)}$$

我们重新总结利用特征方程法求解常系数齐次递推关系的一般方法：

• 写出特征方程
• 求解特征方程
  • 没有重根，根据定理7.4.1直接给出通解
  • 有重根，根据定理7.4.2求出通解
• 将初始条件代入，得到满足初始条件的解

生成函数法

可以参考《组合数学》P146的例子

Part 4 非线性齐次递推关系

迭代求解 & 数学归纳

生成函数

特征方程

1. 求齐次的通解
2. 求非齐次的特解
3. 组合齐次的通解和非齐次的特解，得到非齐次的通解
4. 通过初始条件求得通解中出现的常数值

尝试特解的方法

根据 $ b_n $ 的特点来尝试特解：

$ b_n $ 是 $ n $ 的 $ k $ 次多项式

尝试 $ h_n $ 是 $ n $ 的 $ k $ 次多项式：

• 若 $ b_n = d $ ，尝试 $ h_n = r $ （常数）
• 若 $ b_n = dn + c $ （ $ d,c $ 是常数 ），尝试 $ h_n = rn+s $ （ $h,s $ 是常数）
• 若 $ b_n = an^2 + dn + c $ ，（ $ a,b,c $ 是常数 ），尝试 $ h_n = rn^2 + sn + t $ （ $ r,s,t $ 是常数 ）

$ b_n = d^n $ （ $ d $ 是常数 ）是指数形式

尝试 $ h_n = pd^n $ （ $ p $ 是常数 ）也是指数形式

---

• ← Previous Post
• Next Post →

---