组合数学3-特殊计数序列,指数型母函数

字数统计: 2.8k字 | 阅读时长: 12分

2020-08-14

摘要: 组合数学：特殊计数序列、指数型母函数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在组合数学1-排列组合中我们详细梳理了组合数学的基本模型以及相关公式；在组合数学2-母函数,递推关系中我们详细学习了母函数、递推关系。

本文我们看一下组合数学的第三部分，特殊计数序列和指数型母函数，主要内容如下：

卡特兰数
- 96. 不同的二叉搜索树
- 1259. 不相交的握手
指数型母函数
- 定义
- 基准泰勒展开
- 应用：1234组成多少个5位数
错排问题
- 错排问题的递推公式
- 用指数型母函数求某些非常系数递推关系
- 应用：634. 寻找数组的错位排列
第一类 stirling 数
- 1866. 恰有 K 根木棍可以看到的排列数目
第二类 stirling 数
- 634. 寻找数组的错位排列

卡特兰数

几个例子：

进展序列 1…n，有几种出栈序列
n 个节点构成的二叉搜索树，有多少种
正 n 边形分为不重叠的三角形，有多少种形式
2n 个人排队买票，票价 k 元，n 人拿 k 元面值，n 人拿 2k 元面值。求顺利买票的方案数
Dyck Path: (0, 0) -> (n, n)
合法括号数
Dyck word
n 个人在圆桌上握手，求不相交的握手方法数

1958 年出现卡特兰数的递推式：$C_{n} = \sum_{i=0}^{N-1}C_{i}C_{n-i-1}$

卡特兰数的母函数：$C(x) = \sum_{n=0}^{\infty} C_{n}x^{n}$

卡特兰数的组合数公式： $C_{n} = \dbinom{2n}{n} - \dbinom{2n}{n - 1} = \frac{1}{n + 1}\dbinom{2n}{n} = \prod_{k=2}^{n}\frac{n + k}{k}$

以下是力扣上两道卡特兰数相关的题目：

指数型母函数

二项式定理

母函数可以天然地求组合数，因为根据二项式定理：

$(1 + x)^{n} = 1 + nx + \frac{1}{2}n(n - 1)x^{2} + \cdots + \frac{1}{k!}n(n - 1)\cdots(n - k + 1)^{k} + \cdots$

组合 $\dbinom{n}{k}$ 的母函数就是 $(1 + x)^{n}$

现在的问题是母函数能否求排列 $P(n, k) = \dbinom{n}{k}k!$

将上式嵌入到母函数中：

$\begin{align} (1 + x)^{n} &= \sum\limits_{k=0}\limits^{\infty}\dbinom{n}{k}x^{k} \\ &= \sum\limits_{k=0}\limits^{\infty}\dbinom{n}{k}\frac{k!}{k!}x^{k} \\ &= \sum\limits_{k=0}\limits^{\infty}P(n, k)\frac{x^{k}}{k!} \end{align}$

指数型母函数

对于序列 $a_{0}, a_{1}, a_{2}, \cdots$，构造函数

$G_{e}(x) = a_{0} + \frac{a_{1}}{1!}x + \frac{a_{2}}{2!}x^{2} + \cdots + \frac{a_{k}}{k!}x^{k} + \cdots$

称 $G_{e}(x)$ 为序列 $a_{0}, a_{1}, a_{2}, \cdots$ 的指数型母函数。

母函数有基准的泰勒展开：

$(1 - x)^{-1} = 1 + x + x^{2} + \cdots$

指数型母函数也有基准的泰勒展开：

$e^{x} = \sum\limits_{n=0}\limits^{\infty}\frac{x^{n}}{n!} = 1 + x + \frac{x^{2}}{2!} + \cdots + \frac{x^{n}}{n!} + \cdots$

应用

例1

1, 2, 3, 4 组成多少个 5 位数，其中 1 出现的次数范围 [1, 2]，2 的次数范围 [0, 1], 3 的次数范围 [0, 3], 4 的次数为偶数。

记满足条件的 r 位数个数为 $a_{r}$

则 $a_{1}, a_{2}, \cdots$ 的指数型母函数：

$G_{e}(x) = (\frac{x}{1!} + \frac{x^{2}}{2!})(1 + x)(1 + \frac{x}{1!} + \frac{x^{2}}{2!} + \frac{x^{3}}{3!})(1 + \frac{x^{2}}{2!} + \frac{x^{4}}{4!})$

最终 $x^{5}$ 项为：$215\frac{x^{5}}{5!}$，因此答案为 215

例2

1, 3, 5, 7, 9 组成 n 位数，其中 3, 7 限偶数次， 1, 5, 9 次数无限制，有多少个 n 位数

$G_{e}(x) = (1 + \frac{x^{2}}{2!} + \frac{x^{4}}{4!} + \cdots)^{2}(1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \cdots)^{3}$

利用

$e^{x} = \sum\limits_{n=0}\limits^{\infty}\frac{x^{n}}{n!} = 1 + x + \frac{x^{2}}{2!} + \cdots + \frac{x^{n}}{n!} + \cdots \\ e^{-x} = \sum\limits_{n=0}\limits^{\infty}\frac{x^{n}}{n!}(-1)^{n} = 1 - x + \frac{x^{2}}{2!} + \cdots \\$

可得

$\begin{align} G_{e}(x) &= (\frac{1}{2}(e^{x} + e^{-x}))^{2}(e^{x})^{3} \\ &= \frac{1}{4}(e^{x} + e^{-x})^{2}e^{3x} \\ &= \frac{1}{4}(e^{5x} + 2e^{3x} + e^{x}) \\ &= \frac{1}{4}(\sum\limits_{n=0}\limits^{\infty}\frac{5^{n}}{n!}x^{n} + 2\sum\limits_{n=0}\limits^{\infty}\frac{3^{n}}{n!}x^{n} + \sum\limits_{n=0}\limits^{\infty}\frac{1}{n!}x^{n}) \\ \end{align}$

因此 $x^{n}$ 项为 $\frac{1}{4}(5^{n} + 2 \times 3^{n} + 1)$，答案为 $a_{n} = \frac{1}{4}(5^{n} + 2 \times 3^{n} + 1)$

错排问题

问题描述

实际问题：

n 对男女跳舞，下一曲每个人都必须换舞伴，问有多少种换法。

抽象问题

n 个有序的元素有 $n!$ 中不同的排列，如果一个排列使得所有的元素都不在原来的位置上，则成其为错排。

错排的递推关系

记 n 位的错排数 $D_{n}$，初始值：$D_{0}=1$, $D_{1}=0$, $D_{2}=1$

对于 1 ~ n 的任意数 i: 有两种选择：

分别与除 i 以外其余的 n - 1 个数之一互换，同时另外 n - 2 个进行错排，得到 $(n - 1)D_{n-2}$
除 i 以外其余的 n - 1 个数进行错排，排好后 i 与其中之一互换，得到 $(n - 1)D_{n-1}$

因此递推关系可得：

$D_{n} = (n - 1)(D_{n-1} + D_{n-2}) \\ D_{1}=0, D_{2}=1 \\$

错排的通项公式

公式变形

$D_{n} = (n - 1)(D_{n-1} + D_{n-2}) \\$

这是非常系数递推关系，但该公式可以巧解：

$\begin{align} D_{n} - nD_{n-1} &= -(D_{n-1} + (n-1)D_{n-2}) \\ &= \cdots \\ &= (-1)^{n-1}(D_{1} - D_{0}) \\ &= (-1)^{n} \\ \end{align}$

得到一个新的递推关系：

$D_{n} - nD_{n-1} = (-1)^{n}$

指数型母函数解某些非常系数递推关系

令 $G_{e}(x) = D_{0} + D_{1}x + \frac{D_{2}}{2!}x^{2} + \frac{D_{3}}{3!}x^{3} + \cdots$

将递推公式代入：

$\begin{align} G_{e}(x) &= D_{0} + (D_{0} + (-1)^{1})x + \frac{(D_{1} + (-1)^{2})}{2!}x^{2} + \frac{(D_{2} + (-1)^{3})}{3!}x^{3} + \cdots \\ &= (1 - x + \frac{x^{2}}{2!} - \frac{x^{3}}{3!} + \cdots) + (D_{0}x + \frac{2D_{1}}{2!} + \frac{3D_{2}}{3!} + \cdots) \\ &= e^{-x} + xG_{e}(x) \\ \end{align}$

因此 $G_{e}(x) = \frac{e^{-x}}{1 - x} = \frac{(1 - x + \frac{x^{2}}{2!} - \frac{x^{3}}{3!} + \cdots)}{1 - x}$

进而可以得到：

$\begin{align} D_{n} &= (1 - 1 + \frac{1}{2!} - \cdots \pm \frac{1}{n!})n! \\ &= \sum\limits_{k=0}\limits^{n}(-1)^{k}\dbinom{n}{k}(n - k)! \\ \end{align}$

错排问题应用

N 个人，每个人有一张自己的卡片，将卡片打散后随机分给每个人一张，求每个人都没有拿到自己的卡片的概率
634. 寻找数组的错位排列

Stirling数

Stirling 排列：多重集 {1, 1, 2, 2, …, k, k} 的排列，而重复数字之间的数据都要大于该数，有多少种。

第一类 Stirling 数

问题描述

n 个人排成一个环，分成 m 个环，环内元素的顺序要保持原有顺序，有多少种方法。

等价问题：圆周上有 n 个点，能画出多少个不同的圈(一个点也算是圈)

递推公式

记答案为 $S(n, m)$

$S(n, 0) = 0, S(n, 1) = 1$

考虑从 n-1 到 n，新增的第 n 个元素有两种方案:

n 自己是一个圈，其余 n - 1 形成 m - 1 个圈
n 加入一个已有的圈，因为有序，有 n - 1 个位置可以插入，其余 n - 1 形成 m 个圈

因此可以写出递推公式

$S(n, m) = S(n - 1, m - 1) + (n - 1)S(n - 1, m)$

有符号和无符号的第一类 Striling 数

有的书上是这么写的：

$S(n, m) = S(n - 1, m - 1) - (n - 1)S(n - 1, m)$

唯一的区别是中间的正负号。两种递推关系对应无符号和有符号第一类 Stirling 数。

+ 号的是无符号第一类 Stirling 数, - 号的是有符号第一类 Striling 数。

有符号第一类 Striling 数和无符号第一类 Stirling 数的几何意义不一样

考虑下降阶乘和上升阶乘

下降阶乘

$S(n, m) 对应的是有符号第一类 Striling 数$

$\begin{align} [x]_{n} &= x(x - 1)(x - 2)\cdots(x - n + 1) \\ &= S(n , 0) + S(n, 1)x + S(n, 2)x^{2} + \cdots + S(n, n)x^{n} \end{align}$

上升阶乘

$S(n, m) 对应的是无符号第一类 Striling 数$

$\begin{align} x^{(n)} &= x(x + 1)(x + 2)\cdots(x + n - 1) \\ &= S(n , 0) + S(n, 1)x + S(n, 2)x^{2} + \cdots + S(n, n)x^{n} \end{align}$

对 $[x]_{n}$ 做一些推导可以得到 $x^{k}$ 的系数为 $S(n, k - 1) - nS(n, k) = S(n + 1, k)$，中间是减号

例题

1866. 恰有 K 根木棍可以看到的排列数目

题解可以参考文章 leetcode第241场周赛。

第二类 Stirling 数

问题描述

n 个球分为 k 组，组内无顺序，求方案数。

递推公式

记答案为 $S(n, k)$，$S(n, 0) = 0, S(n, 1) = 1, S(n, n) = 1$

考虑 $S(n, 2)$ 将无区别的两个盒子编程有区别的两个盒子。从 1, …, n 中取出某个数 i，可以把盒子分为两种：有 i 的和无 i 的。此后剩下的 n - 1 个球军有两种选择，所有 $S(n, 2) = 2^{n-1} - 1$，-1 是把空盒的情况减掉。

考虑 $S(n, m)$，仿照上面的方法，先取出一个球 i，有两种情况

i 独占 1 盒，剩下的 n - 1 个求放在 m - 1 个盒子.
i 进入了已有的一盒，剩下的 n - 1 个球已经放在了 m 个盒子

于是可以写出递推关系：

$S(n, m) = S(n - 1, m - 1) + mS(n - 1, m)$

用指数型母函数求解递推公式

如果组(盒子)之间有区别，n 个有标志的球放进 m 个有区别的盒子，则方案数为 $m!S(n, m)$。

相当于 m 个有标志的元素取 n 个做允许重复的排列，既然是排列，可以考虑指数型母函数

$\begin{align} G_{e}(x) &= (x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \cdots)^{m} = (e^{x} - 1)^{m} \\ &= \sum\limits_{h=1}\limits^{m}\dbinom{m}{h}(-1)^{h}e^{(m-h)x} \\ \end{align}$

其中

$e^{(m-h)x} = \sum\limits_{n=0}\limits^{\infty}\frac{(m-h)^{n}}{n!}x^{n}$

因此

$G_{e}(x) = \sum\limits_{n=0}\limits^{\infty}\frac{x^{n}}{n!}\sum\limits_{h=1}\limits^{m}\dbinom{m}{h}(-1)^{h}(m-h)^{n}$

通项公式

$S(n, m) = \frac{1}{m!}\sum\limits_{h=1}\limits^{m}\dbinom{m}{h}(-1)^{h}(m-h)^{n}$

注意：指数型母函数可以解决很多非线性常系数递推关系，但不是所有的非线性常系数递推关系都可解。