菲比Blog

点赞 91 阅读 162 评论 0 点踩 3

$0.0$ 前言

本文完成仓促，必然存在一些错误，希望读者阅读时多加思考，指出疑问和错误。

文章简述了组合数学的理论性内容，仅仅作为兴趣引入和入门学习，作者很菜，比不上数学大手子，请轻点喷。

$1.0$ 排列组合基础

$1.1$ 加法原理、乘法原理

对于事件 $A$，有 $n$ 个解决方案，每个方案有数量 $a_1,a_2,a_3……a_n$ 对于解决事件 $A$ 的总方案，有

\[\sum_{i=1}^{n}{a_i} \]

上述计算方法称为加法原理。

对于事件 $A$，解决事件需要完成 $n$ 个子任务，每个子任务有方案数量 $a_1,a_2,……a_n$ 对于解决 $A$ 的方案，有 $$ \Pi_{i=1}^{n}{a_i}$$

上述计算方法称为乘法原理。

$1.2$ 基本排列组合公式

在 $1,2,3……,n$ 中，取出 $m$ 个数并按取出顺序放在 $a_1,a_2,……,a_m$ 中，两个方案不同当且仅当至少存在一个位置 $a_i$ 在两个方案里不同。其方案数被称为从 $n$ 个元素中选取 $m$ 个元素的 排列数，记作 $A_{n}^{m}$ 或者 $P_{n}^{m}$。

有公式 $$A_{n}^{m} = \frac{n!}{(n-m)!}$$

在 $1,2,3……,n$ 中，取出 $m$ 个数，两个方案不同当且仅当至少存在一个数 $x$ 在两个方案中不同时存在。其方案数被称为从 $n$ 个数中选取 $m$ 个数的 组合数，记作 $C_{n}^{m} 或者 \binom{n}{m} $

有公式 $$ \binom{n}{m}=\frac{n!}{m!(n-m)!}$$

以上证明从略。

特殊的，一个序列的所有排序方案 $A_{n}^{n}$ 被称为全排列，等于 $n!$

$2.0$ 常见组合数模型

$2.1$ 插板法 $1$

对于方程 $n=\sum_{i=1}^{k} x_i$ 求所有 $x_i \ge 1$ 的解的个数。

考虑将模型转化为在 $n$ 个 $1$ 的间隙中插入 $k-1$ 个板子，一个空隙可以插一个板子，显然，这个问题的方案数是 $$ \binom{n-1}{k-1}$$

对于每两个板子或者边界的一段 $1$ 的和视为方程的一个 $x_i$ 的解，那么插板的方案等价于方程的解的方案。

$2.2$ 插板法 $2$

对于方程 $n=\sum_{i=1}^{k}{x_i}$ 求所有 $x_i \ge 0 $ 的解的方案数。

对于这个问题，相当于在上面问题的基础上使一个空隙中可以插入任意多个板子，直接求解是困难的。

我们考虑构造一个新的方程，使 $x'_i = (x_i + 1)$，构造方程 $n+k = \sum^{k}_{i=1} x'_i$，其中 $x'_i \ge 1 $ 那么这个新方程的解的方案数就和插板法 $1$ 中的问题等价了。

由于我们的新方程仅仅在原方程的基础上加上了常数，所以容易证明构造方程与原方程的解的个数相等。答案为 $$ \binom{n+k-1}{k-1}$$

$2.3$ 插板法 $3$

再次推广，若上述方程的每个解 $x_i$ 都有限制 $x_i \ge a_i $，求解方案数个数。

类似地，我们也可以采用插板法 $2$ 的构造方程的方法。

使 $ x'_i=x_i-a_i + 1$，剩下的过程从略。

答案为 $$\binom{n-\sum{a_i}+k-1}{n-\sum{a_i}}$$

$2.4$ 不相邻排列

给出长度为 $n$ 的排列，求从中选出 $k$ 个数，使其中的任意两个数在排列中不相邻的方案数。

相当于选择 $k$ 个断点 (可以是起点或终点) 将长度为 $n-k$ 的序列截断，并使每段长度至少为 $1$。

答案为 $$\binom{n-k+1}{k}$$

$3.0$ 常见的组合数公式

1

\[\binom{n}{m}=\binom{n}{n-m} \]

证明：考虑组合意义。

2

\[\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \]

证明：将原式展开为分式后拆出一个 $\frac{n}{k}$ 即可。

3

\[\binom{n}{m}=\binom{n-1}{m} + \binom{n-1}{m-1} \]

证明：根据组合意义，从 $n$ 个中选 $m$ 个，可以是在 $n-1$ 个里全部选完或者钦定选择第 $n$ 个在 $n-1$ 个里选 $m-1$ 个。

代数的方法可以拆掉左右两边的式子，将右边的式子凑成左边的。

上式常用于组合数的递推求解，也是杨辉三角的公式。

4

\[\binom{n}{r}\binom{r}{s} = \binom{n-s}{r-s} \]

证明：

组合意义上，从 $U$ 的任一大小为 $r$ 子集 $R$ 中选择 $s$ 个元素的方案数，相当于确定了集合 $S$ 并在剩下的元素中再选出 $r-s$ 个元素组成集合 $R$。

代数上可以拆开式子凑项。

5

\[\sum^{n}_{i=0}{\binom{n}{i}} = 2^n \]

证明：根据组合意义，左边式子的意义是在 $n$ 个里选任意多个的方案数，那么每个位置有选或者不选两个情况，根据乘法原理，$n$ 个的方案就是 $2^n$。

代数方法需要用到二项式定理，将在下面给出。

6

\[(a+b)^n = \sum_{i=0}^{n}{\binom{n}{i}a^{n-i}b^i} \]

该式称为二项式定理或牛顿定理，是证明、推导组合公式的优秀定理。

证明：利用数学归纳法可以证明。

当 $n=1$ 时，显然成立。

当 $n=k+1$ 时，假设存在 $(a+b)^k = \sum_{i=0}^{k}{\binom{k}{i}a^{k-i}b^i}$，那么 $(a+b)^n = (a+b) \times \sum_{i=0}^{k}{\binom{k}{i}a^{k-i}b^i}$，整理上式得

\[a^{k+1} + \sum_{i=1}^{k}{\binom{k}{i}a^{k-i+1} b^i} + \sum_{i=0}^{k}{\binom{k}{i}a^{k-i}b^{i+1}} \]

令 $j=i+1$ 得

\[a^{k+1} + \sum_{i=1}^{k}{\binom{k}{i}a^{k-i+1} b^i} + \sum_{j=1}^{k}{\binom{k}{j-1}a^{k-j+1}b^{j}} \]

合并得

\[\sum_{i=0}^{k+1}{\binom{k+1}{i}a^{n-i}b^i} \]

证毕。

下面利用二项式定理证明公式 $5$

\[(1+1)^n = \sum^{n}_{i=0}{\binom{n}{i}} = 2^n \]

7

\[\sum_{i=0}^{k}{\binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k}} \]

上式为范德蒙德恒等式或范德蒙德卷积。

证明：

利用组合意义可以考虑将一个大小为 $n+m$ 的集合中选 $k$ 个元素的问题转化为从两个集合中总和为 $k$ 的元素。

利用代数方法证明需要利用二项式定理。

\[(a+1)^{n+m}=\sum_{k=0}^{n+m}{\binom{n+m}{k}x^k} \]

拆开指数得

\[(a+1)^n \times (a+1)^m = \sum_{i=0}^{n}{\binom{n}{i}x^i} \times \sum_{j=0}^{m}{\binom{m}{j} x^j} \]

合并得

\[\sum_{i=0}^{n}\sum_{j=0}^{m}{ \binom{n}{i}\binom{m}{j}x^{i+j}} \]

令 $s=i+j$ 得

\[\sum_{s=0}^{n+m}\sum_{i=0}^{n}{\binom{n}{i}\binom{m}{s-i}x^s} \]

则有

\[\sum_{k=0}^{n+m}{\binom{n+m}{k}x^k} = \sum_{k=0}^{n+m}\sum_{i=0}^{n}{\binom{n}{i}\binom{m}{k-i}x^k} \]

当两式相等时，当且仅当

\[\binom{n+m}{k}=\sum_{i=0}^{n}{\binom{n}{i}\binom{m}{k-i}} \]

证毕。

下面给出范德蒙德卷积的一些推论

8

\[\sum_{i=0}^{k}{\binom{i}{m}\binom{k-i}{n}} = \binom{k+1}{m+n+1} \]

证明：

拿出 $k$ 个小球，每次将其分成两部分，一部分选 $n$ 个，另一部分选 $m$ 个，相当于在整个小球序列中选择 $n+m$ 个球和一个分割线，两边相等就是上式。

9

\[\sum_{i=-r}^{s}{\binom{n}{r+i}\binom{m}{s-i}} = \binom{n+m}{r+s} \]

证明从略。

10

\[\sum_{i=1}^{n}{\binom{n}{i}\binom{n}{i-1}} = \binom{2n}{n-1} \]

证明：

将原式恒等变换得

\[\sum_{i=1}^{n}{\binom{n}{n-i}\binom{n}{i-1}} = \binom{2n}{n-1} \]

设 $ j= i-1 $

\[\sum_{j=0}^{n-1}{\binom{n}{n-1-j}\binom{n}{j}} \]

对于该式的证明同公式 $7$。

值得注意的是，类似上式的式子化为类似范德蒙德的时候都可以利用类似的方法。同时需要注意求和的枚举范围和枚举上界与卷积后的关系。

11

\[\sum_{j=0}^{k}{\binom{k}{j}^2 \binom{n+2k-j}{2k}} = \binom{n+k}{k}^2 \]

上式为李善兰恒等式的特殊形式。

证明：

首先利用公式 $7$ 证明

\[\sum_{i=0}^{n}{\binom{p}{i}\binom{q}{i}\binom{n+i}{p+q}} = \binom{n}{p}\binom{n}{q} \]

由公式 $7$ 可知

\[\sum_{i=0}^{n}{\binom{p}{i}\binom{q}{i}\binom{n+i}{p+q}} = \sum_{i=0}^{n}{\binom{p}{i}\binom{q}{i}\sum_{j=1}^{p+q}{\binom{i}{j}\binom{n}{p+q-j}}} \]

根据数学归纳法，当 $p=q,n=0$ 时，显然成立。

接着，如果 $p=q,n=m+1$ 时，假设 $n=m$ 时成立，可以证明成立。

接着，如果 $p=q+1,p=q-1$ 时，成立。

所以，可以推广成立。

对等式右边构造多项式得

\[(x-1)^{p+q}=(x-1)^p \times (x-1)^q = \sum_{i=0}^{p+q}\binom{n}{p}\binom{n}{q} \]

将 $x=-1$ 带入得

\[\binom{n}{p}\binom{n}{q} = \binom{n+p}{p}\binom{n+q}{q} \]

将等式左边换元，令 $ j=p+q-i $，得

\[\sum_{j=0}^{p}{\binom{p}{j} \binom{n+p+q-j}{p+q}} = \binom{n+p}{p}\binom{n+q}{q} \]

当 $p=q$ 时，该式即为原式。

证毕。

根据范德蒙恒等式，我们还能证明许多类似的结论，这里不一一列举。

12

\[\sum_{i=1}^{n}{i\binom{n}{i}} = n2^{n-1} \]

考虑将组合数构造为多项式形式，利用二项式定理构造出

\[(1+x)^n= \sum_{i=0}^{n}{\binom{n}{i}x^i} \]

对该式子求导得

\[n(1+x)^{n-1}=\sum_{i=1}^{n}{i\binom{n}{i}x^{i-1}} \]

带入 $x=1$ 得

\[n2^{n-1}=\sum_{i=1}^{n}{i\binom{n}{i}} \]

证毕。

13

\[n(n+1)2^{n-2} = \sum_{i=0}^{n}{i^2\binom{n}{i}} \]

证明：

求二阶导即可。

$4.0$ 容斥原理

$4.1$ 容斥原理的基本式

给定全集 $U$ 对于每个集合 $S_1,S_2……S_n$ 求其并集。

我们由两个集合 $S_1,S_2$ 开始考虑，显然

\[ |S_1 \cup S_2| = |S_1|+|S_2| - |S_1 \cap S_2| \]

考虑三个，发现如果单纯减去两两间的交集会导致三个的交集被多减去一次，所以我们把它加回来。

\[|S_1 \cup S_2 \cup S_3| = |S_1|+|S_2|+|S_3| - |S_1 \cap S_2| - |S_1 \cap S_3| - |S_2 \cap S_3| +|S_1 \cap S_2 \cap S_3| \]

那么我们发现求 $n$ 个元素的并集就是

\[|\bigcup_{i=1}^{n}{S_i}| = \sum_{i=1}^{n}{(-1)^{i-1} \sum_{a_j<a_{j+1}}{|\bigcap_{j=1}^{i}{S_j}|}} \]

更加普遍的，我们给出容斥原理的函数定义。

设关于两函数 $f(x),g(x)$，同时存在集合关系 $T \subseteq S$。

若两函数间满足

\[f(S) = \sum_{T \subseteq S}{g(T)} \]

就存在

\[g(S) = \sum_{T \subseteq S}{(-1)^{|S|-|T|} f(T)} \]

下面给出这个上述基本定义在集合论上的证明

设 $g(T)$ 表示集合中恰好有 $|T|$ 个属性的元素个数，$f(T)$ 表示集合中至多有 $|T|$ 个属性的元素个数。

\[f(S)= \sum_{i=1}^{n}{(-1)^{i-1} \sum_{a_j<a_{j+1}}{|\bigcap_{j=1}^{i}{S_j}|}} \]

其中

\[\sum_{i=1}^{n}{(-1)^{i-1} \sum_{a_j<a_{j+1}}{|\bigcap_{j=1}^{i}{S_j}|}} = \sum_{T \subseteq S}{g(T)} \]

所以 $f(x)$ 与 $g(x)$ 满足

\[f(S) = \sum_{T \subseteq S}{g(T)} \]

若已知 $f(S)$，考虑反向容斥求得 $g(S)$

\[g(S) = \sum_{T \subseteq S}{(-1)^{|S|-|T|}f(T)} \]

所以，定义在集合上的函数 $f(x),g(x)$，满足关系

\[f(S) = \sum_{T \subseteq S}{g(T)} \Longleftrightarrow g(S) = \sum_{T \subseteq S}{(-1)^{|S|-|T|} f(T)} \]

证毕。

上述互推关系类似于数列的演绎和反演，在之后二项式反演的证明中也会用到类似的集合论证明方法。

对于容斥基本式的证明可以使用二项式定理计算每个集合的系数，若全部为 $1$ 即可得证，这里不再详细证明。

$4.2$ 容斥原理简单应用

限制上界的不定方程

给定方程 $n=\sum_{i=1}^{k}x_i$，求满足 $x_i\le a_i$ 的解的个数。

在 $2.3$ 我们给出了限制为 $x_i \ge a_i$ 的解的个数的计算方法，接下来，我们利用之前的方法加以容斥求解。

设全集 $|U|$ 为 $x_i$ 为非负整数的解的个数，$S_i$ 表示对于 $x_i$ 的合法解的个数，显然有

\[ans=|\bigcap_{i=1}^{k}{S_i}| = |U| - |\bigcup_{i=1}^{k}{\complement_{U}S_i}| \]

后者即为 $x_i \ge a_i+1$ 的解的个数。

考虑容斥展开，对于 $k$ 个集合的并，其组合意义是对于这 $k$ 个 $x_i$ 有下界而其余无下界，也可以是下界为 $0$ 所以，根据 $2.3$ 我们有

\[ans=\binom{n+k-1}{k-1} - \sum_{i=1}^{k} (-1)^{i-1} \sum_{a_j<a_j+1}{{\binom{n-\sum{a_j}+k-1}{n-\sum{a_j}}}} \]

错位排列

下面给出一个经典问题。

给出一个长度为 $n$ 的有序排列，求打乱后没有一个元素在原来的位置上的方案数。

考虑容斥，设所有排列为全集 $U$，$S_i$ 为 $i$ 不在原位的方案数。

有

\[ans=|U|-|\bigcup_{i=1}^{n}\complement_{U}S_i| \]

展开容斥有

\[ans=|U|-\sum_{i=1}^{n}{(-1)^{i-1}\sum_{a_j<a_{j+1}}{|\bigcap_{j=1}^{i}\complement_{U}S_j|}} \]

考虑式子 ${|\bigcap_{j=1}^{k}\complement_{U}S_i|}$ 的组合意义，即为钦定 $k$ 个数固定在原位，其他数随意排序的方案数，即为 $(n-k)!$。

那么

\[\sum_{a_j<a_{j+1}}{|\bigcap_{j=1}^{k}\complement_{U}S_j|} = \binom{n}{k} (n-k)! \]

带回原式化简得

\[ans=n!-n!\sum_{i=1}^{n}{\frac{(-1)^{k-1}}{k!}} \]

在这里，我们给出错位排列的递推公式，由于其解法不在本篇的范围，所以不给出证明，读者可利用数学归纳法或者直接推导自证。

\[D_1=0,D_2=1 \]

\[D_n=(n-1)(D_{n-1}+D_{n-2}) \]

$4.3$ 抽屉原理

对于 $n$ 个盒子和 $n+1$ 个物品，将物品放入盒子，至少有一个盒子中有大于 $1$ 个物品。

推广得到，$n$ 个物品随机划分为 $k$ 组，至少有一组内物品数大于等于 $\lceil \frac{n}{k} \rceil$

不给出证明。

$5.0$ 二项式反演

给定数列 $f(x),g(x)$，若存在计算方法 $\phi(f(x)) = g(x)$ 则称其为 $f(x)$ 到 $g(x)$ 的演绎。若还有 $ \rho(g(x))=f(x) $ 则称其为 $f(x)$ 到 $g(x)$ 的反演。

$5.1$ 二项式反演

\[f(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{i}g(i)} \Longleftrightarrow g(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{i}f(i)} \]

证明

给出一个集合论的证明方法。

设全集 $U$ 内存在 $n$ 个交集、并集大小都相等的集合 $S_i$，$g(x)$ 表示任意 $x$ 个元素的并集大小， $f(x)$ 表示任意 $x$ 个元素的交集大小。

考虑如何表示 $f(n),g(n)$

\[f(n)=|\bigcap_{i=1}^{n}{S_i}|=|U|-|\bigcup_{i=1}^{n}{\complement_{U}S_i}| = |U|-\sum_{i=0}^{n}{(-1)^i\sum_{a_j<a_j+1}{|\bigcap_{j=1}^{i}\complement_{U}s_j|}} \]

最后一个式子的含义为 $n$ 个集合补集的交集，根据德摩根定理，就等于原集的并集，根据容斥有

\[f(n) = \sum_{i=0}^{n}{(-1)^i\binom{n}{i}g(i)} \]

同理，利用性质也可以反推出 $g(n)$ 与 $f(x)$ 的关系。
得到

\[g(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{i}f(i)} \]

证毕。

给出一个代数证明的思路，由于过程中没有用到复杂构造或者思路，所以不再详细证明。

若存在

\[f(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{i}g(i)} \]

并使

\[g(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{i}f(i)} \]

成立，可以将 $g(x)$ 表示为

\[g(x)=\sum_{i=0}^{x}{(-1)^i\binom{x}{i}f(i)} \]

带入后即为

\[f(n)=\sum_{i=0}^{n}{(-1)^i\binom{n}{j}\sum_{j=0}^{i}{(-1)^j\binom{i}{j}f(j)}} \]

交换枚举顺序并将除 $f(j)$ 项视为系数，证明系数 $a_j = [j=n]$ 即可，需要用到组合数与多项式间转化。

除了一般形式外，通过换元我们还有另一种形式

\[g(n)=\sum_{i=0}^{n}{\binom{n}{i}f(i)} \Longleftrightarrow f(n)=\sum_{i=0}^{n}{(-1)^{n-i}\binom{n}{i}g(i)} \]

我们发现，二项式反演具有对称性，而在集合论的推导中，我们使用了交集和补集进行证明。那如果我们将上面的集合由选取改为钦定不选取，问题就转化为在全集中至少选取 $n$ 个元素了。容易猜想出一个式子。

\[f(n)=\sum_{i=n}^{N}{\binom{i}{n}g(i)} \]

事实上，的确存在反演

\[ f(n)=\sum_{i=n}^{N}{\binom{i}{n}g(i)} \Longleftrightarrow g(n)=\sum_{i=n}^{N}{(-1)^{i-n}\binom{i}{n}f(i)} \]

证明是基本一致的，仅仅是构造函数的含义不同，请读者自证。

$5.2$ 二项式反演的应用

错位排列

错位排列的描述请翻阅 $4.2$。

设 $f(x)$ 为 $x$ 个数的错位排列方案数，$g(x)$ 表示至多 $x$ 个数错位的排列数。

有

\[g(n)=\sum_{i=0}^{n}{\binom{n}{i}f(i)} \]

同时，$g(x)$ 的直接计算是简单的，就是钦定 $n-x$ 个数在原位的方案数，即为 $x!$。

根据二项式反演

\[f(x)=\sum_{i=0}^{n}{(-1)^{n-i}\binom{n}{i}g(i)} \]

带入 $g(i)=x!$ 即可。

可以看到，二项式反演在解决恰好问题难以直接解决而带有上下界的问题却容易解决的问题时比较优秀。

二类斯特林数

n个不同的球放入m个有标号盒子，要求每个盒子非空的方案数。

关于斯特林数，在下一章会详细讲述，这里仅仅作为问题参考，注意，本问题不是第二类斯特林数，仅仅是部分推导。

设 $f(x)$ 表示放入 $n$ 个球恰好使 $x$ 个箱子非空的方案数 $g(x)$ 表示放入 $n$ 个球至多使 $x$ 个箱子非空的方案数。

有

\[g(m)=\sum_{i=0}^{m}{\binom{m}{i}f(i)} \]

考虑 $g(x)$ 的组合意义，将 $n$ 个球随意放入 $x$ 个箱子，就有 $g(x)=n^x$

于是有

\[f(m)=\sum_{i=0}^{m}{(-1)^{m-i}\binom{m}{i}g(i)} \]

得出

\[f(m)=\sum_{i=0}^{m}{(-1)^{m-i}\binom{m}{i}n^i} \]

$5.3$ 高维二项式反演

在上面，我们给出了单元函数 $f(x),g(x)$ 之间的关系，那么，对于多元函数 $f(x,y),g(x,y)$ 之间是否也存在类似的关系？

给出二维二项式反演

\[f(n,m)=\sum_{i=0}^{n}{\sum_{j=0}^{m}\binom{n}{i}\binom{m}{j}g(i,j)} \Longleftrightarrow g(n,m)=\sum_{i=0}^{n}{\sum_{j=0}^{m}\binom{n}{i}\binom{m}{j}(-1)^{(n-i)+(m-j)}f(i,j)} \]

证明方法参考单元二项式反演的代数证明。事实上，到这里我们已经很难再利用组合意义证明这样的式子。

同样的，我们可以得到 $n$ 维二项式反演，即枚举每一位，按照上面的方法展开。

$6.0$ 两类斯特林数

$6.1$ 一类斯特林数

将 $n$ 个数划分为 $k$ 个按顺序不同的环的方案数就是一类斯特林数，记作 ${n \brack k}$

对于一类斯特林数，并没有有效通项公式，只能递推求解，给出递推式

\[{n \brack k} = {n-1 \brack k-1} + (n-1){n-1 \brack k} \]

证明：

对于新加入的元素，它可以自己成环，有方案数 ${n-1 \brack k-1}$，或者加入到别的环中，考虑加入到别的环中的方案数等价于将环钦定方向后这个元素的后继的方案数，显然有 $n-1$ 个后继，成环方案有 ${n-1 \brack k}$ 种，即有方案数 $(n-1){n-1 \brack k}$。

一类斯特林数还有求和公式

\[\sum_{i=0}^{n}{n \brack i} = n! \]

证明：

钦定环的顺序并构造后继序列，那么一种 $n$ 个数的排列的意义就是 $i$ 的后继是 $a_i$，对应着一组合法的 $n$ 个数，$k$ 个环的方案（$k = \sum_{i=1}^{n}{[a_i=i]}$）显然的，全排列即为所求，故答案为 $n!$

$6.2$ 二类斯特林数

将 $n$ 个数无重复的划分为 $k$ 个子集的方案数就是二类斯特林数，记作 ${n \brace k}$

在 $5.2$ 中我们证明了若给 $k$ 个子集编号的方案数，而对于二类斯特林数是无标号的，所以二类斯特林数有通项公式

\[{n \brace k} = \frac{1}{k!}\sum_{i=0}^{k}{(-1)^{k-i}\binom{k}{i}n^i} \]

对于二类斯特林数，还有递推式

\[{n \brace k} ={n-1 \brace k-1} + k {n-1 \brace k} \]

证明：

多一个元素，可以插入原有的非空集合中，有 $k {n-1 \brace k}$ ，或者单开一个集合单独放下，有
${n-1 \brace k-1}$，相加即可。

或者利用通项公式暴力拆解也可以证明。

我们称 ${n \brace 1},{n \brace 2},{n \brace 3},……,{n \brace n}$ 为同行二类斯特林数，可以卷积 $O(n\log{n})$ 求出。

我们称 ${1 \brace k},{2 \brace k},{3 \brace k},……,{k \brace k}$ 为同列二类斯特林数，可以用指数生成函数 $O(n\log{n})$ 求出。

$6.3$ 斯特林与数的幂

定义上升幂 $x^{ \overline{m}} = \Pi_{i=0}^{m-1}{x+i}$

定义下降幂 $x^{ \underline{m}} = \Pi_{i=0}^{m-1}{x-i}$

有公式

\[x^{ \overline{-m}} = x^{ \underline{m}} \]

\[n^{\overline{a+b}} = x^ {\overline{a}} (x+a)^{\overline{b}} \]

\[n^{\underline{a+b}} = x^ {\underline{a}} (x-a)^{\underline{b}} \]

\[x^{\underline{m}} = (-1)^m (-x)^{ \overline{m}} \]

给出上升幂到普通幂的转化

\[x^{\overline{n}} = \sum_{k=0}^{n}{{n \brack k} x^k} \]

证明：

由 $6.2$ 知，一类斯特林具有递推式。

考虑数学归纳法。

$n=0$ 时，显然成立。

当 $n=m+1$ 时，假设 $n=m$ 成立，证明

\[(x+m)\sum_{k=1}^{m}{{m \brack k} x^k} = \sum_{k=0}^{m+1}{{m+1 \brack k} x^k} \]

拆解右侧斯特林数得

\[\sum_{k=0}^{m+1}{{m \brack k-1} x^k} + m\sum_{k=0}^{m}{{m \brack k} x^k} \]

令 $i=k-1$

\[x\sum_{i=0}^{m}{{m \brack i} x^i} + m\sum_{k=0}^{m}{{m \brack k} x^k} \]

统一枚举变量，合并得

\[(x+m)\sum_{k=0}^{m}{{m \brack k} x^k} \]

证毕。

同样利用数学归纳法，你可以证明下降幂转普通幂

\[x^{\underline{n}} =\sum_{k=0}^{n}{(-1)^{n-k}{n \brack k}x^k} \]

相应的，普通幂也可以转上升幂或者下降幂

\[x^n=\sum_{k=0}^{n}{{n \brace k}(-1)^{n-k}x^{\overline{k}}} \]

\[x^n=\sum_{k=0}^{n}{{n \brace k}x^{\underline{k}}} \]

给出第二个式子的组合意义证明

考虑等式左边是将 $n$ 个数随意填入 $x$ 个有编号盒子。

将右边稍微变形

\[\sum_{k=0}^{n}{\binom{x}{k}{n \brace k}k!} \]

这个式子的含义是钦定 $1,2,3……n$ 个盒子一定要填的方案数，求和之后就是左边的含义。

代数法仍然可以数学归纳。

$6.4$ 斯特林反演

发现三种幂将两类斯特林数建立了联系，事实上它们间的联系还可以推广到函数上。

给出斯特林反演

\[f(n)=\sum_{k=0}^{n}{{n \brack k}g(k)} \Longleftrightarrow g(n)=\sum_{k=0}^{n}{(-1)^{n-k}{n \brace k}f(k)} \]

\[f(n)=\sum_{k=0}^{n}{{n \brace k}g(k)} \Longleftrightarrow g(n) = \sum_{k=0}^{n}{(-1)^{n-k}{n \brack k} f(i)} \]

证明方法类似二项式反演，这里不详细证明，仅给出思路和关键步骤。

考虑将普通幂转化为上升幂再带入回上升幂公式。

\[x^{\overline{n}}=\sum_{k=0}^{n}\sum_{i=0}^{k}{{n \brack k}{k \brace i}(-1)^{k-i}x^{\overline{i}}} \]

定义 $f(x),g(x)$

\[f(x)=x^{\overline{n}} \]

\[g(x)=\sum_{i=0}^{k}{k \brace i}(-1)^{k-i}x^{\overline{i}} \]

带入到反演 $1$ 的右边式子。

证明其成立即可。

一种证明思路是证明下式成立

\[\sum_{i=k}^{n}{{n \brace i}{i \brack k}(-1)^{n-i}} = [k=n] \]

相同的反演 $2$ 的证明仅仅是改变了套用公式（上升幂改为下降幂），你同样可以得到类似的式子

\[\sum_{i=k}^{n}{{i \brace k}{n \brack i}(-1)^{n-i}} = [k=n] \]

请读者自行完成后续证明。

$6.5$ 向实数推广

我们首先对组合数进行实数意义的推广

\[\binom{r}{n} =\frac{r^{\underline{n}}}{n!} \]

$r$ 可以取任意实数。

那么，我们可以推广二项式定理

\[(x+y)^r=\sum_{i \ge 0}{\frac{r^{\underline{i}}x^iy^{r-i}}{i!}} \]

上升幂的二项式定理

\[(x+y)^{\overline{n}}=\sum_{i=0}^{n}{\binom{n}{i}x^{\overline{i}}y^{\overline{n-i}}} \]

那么，我们就可以利用二项式定理将实数组合数转化为多项式形式。

更为广泛的，由于组合数被定义到了实数域，它就具有了连续性。将其推广至函数上是自然的。
我们同样可以定义其导数，积分。

在调和级数上，实数组合数同样有被定义。

由于这些内容已经超出基本组合数学的内容，在这里不做展开（好吧，就是我不会）

posted @ 2026-02-03 feibi 阅读(162) 评论(0) 点赞(91)

请先登录

登录发表评论

文章分类

文章标签

\(0.0\) 前言

\(1.0\) 排列组合基础

\(1.1\) 加法原理、乘法原理

\(1.2\) 基本排列组合公式

\(2.0\) 常见组合数模型

\(2.1\) 插板法 \(1\)

\(2.2\) 插板法 \(2\)

\(2.3\) 插板法 \(3\)

\(2.4\) 不相邻排列

\(3.0\) 常见的组合数公式

1

2

3

4

5

6

7

8

9

10

11

12

13

\(4.0\) 容斥原理

\(4.1\) 容斥原理的基本式

\(4.2\) 容斥原理简单应用

限制上界的不定方程

错位排列

\(4.3\) 抽屉原理

\(5.0\) 二项式反演

\(5.1\) 二项式反演

\(5.2\) 二项式反演的应用

错位排列

二类斯特林数

\(5.3\) 高维二项式反演

\(6.0\) 两类斯特林数

\(6.1\) 一类斯特林数

\(6.2\) 二类斯特林数

\(6.3\) 斯特林与数的幂

\(6.4\) 斯特林反演

\(6.5\) 向实数推广