组合数学再基础

之前好像写过「组合数学基础」,在这里再来堆点柿子。

1 Stirling 数

1.1 定义

众所周知,Stirling 数有两类,分别是:

$$ \begin{align} \begin{bmatrix}n\newline m \end{bmatrix} = \begin{bmatrix}n-1\newline m-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\newline m \end{bmatrix} \newline \begin{Bmatrix}n\newline m \end{Bmatrix}=\begin{Bmatrix}n-1\newline m-1\end{Bmatrix}+m \begin{Bmatrix}n-1\newline m \end{Bmatrix} \end{align} \tag1 $$

其中 $n,m\in \mathbb N$,它们的边界均是 $S(0,0)=S(1,1)=1,S(1,0)=0$。

接下来介绍 Stirling 数的性质。

1.2 常幂展开

一个组合意义显然的柿子:

$$ \begin{align} n^m &= \sum\limits_{k=0}^m \begin{Bmatrix}m\newline k \end{Bmatrix}k! \dbinom{n}{k} \tag2 \newline &= \sum\limits_{k=0}^m \begin{Bmatrix}m\newline k\end{Bmatrix} n^{\underline{k}} \tag{3} \end{align} $$

其中 $n,m\in\mathbb N$,$(3)$ 式通常被称为 常幂展开

1.3 Stirling 反演

$$ f(n) = \sum\limits_{k=0}^n \begin{Bmatrix}n\newline k\end{Bmatrix} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^{n - k} \begin{bmatrix}n\newline k\end{bmatrix} f(k) \tag{4} $$

其中 $n\in \mathbb N$,$(4)$ 式通常被称为 Stirling 反演公式。

1.4 阶乘幂展开

对 $(3)$ 应用 $(4)$ 式得:

$$ n^{\underline m}= \sum\limits_{k=0}^m (-1)^{m-k} \begin{bmatrix}m\newline k\end{bmatrix} n^k \tag{5} $$

可以证明有:

$$ n^{\overline m}= \sum\limits_{k=0}^m \begin{bmatrix}m\newline k\end{bmatrix} n^k \tag{6} $$

其中 $n,m\in\mathbb N$,$(5),(6)$ 两式被称作阶乘幂展开。

2 组合数

2.1 定义

众所周知,小葱同学擅长计算,尤其擅长计算组合数,但是这跟本文的主题并没有什么关系。

小葱同学擅长计算的组合数定义为:

$$\dbinom{n}{m}=\begin{cases} 0, \text{ }m>n\text{ or }m<0\newline \dfrac{n^{\underline m}}{m!},\text{ otherwise} \end{cases}$$

其中 $n\in \mathbb R,m\in \mathbb Z$。当 $n,m$ 均是非负整数且 $m\le n$ 时,它满足递推式:

$$\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}$$

2.2 二项式定理

$$(x+y)^k = \sum\limits_i \dbinom{k}{i} x^i y^{k-i} \tag{7}$$

其中 $k\in \mathbb R$,$(7)$ 式被称作二项式定理。

2.3 组合恒等式

组合恒等式 I

在 $(7)$ 式中令 $x=y=1$ ,得:

$$\sum\limits_i \dbinom{k}{i} = 2^k \tag{8}$$

其中 $k\in \mathbb R$。

组合恒等式 II

$$\sum\limits_i \dbinom{k}{i}[2|i] =\sum\limits_i \dbinom{k}{i}[2\nmid i] = 2^{k-1} \tag9$$

其中 $k\in \mathbb R$,证明显然。

组合恒等式 III

$$\dbinom{n}{k}\dbinom{k}{j} = \dbinom{n}{j} \dbinom{n-j}{k-j} \tag{10}$$

其中 $n,k,j\in \mathbb Z$,证明显然。

吸收公式

$$ \begin{align} \dfrac{n}{m}\dbinom{n-1}{m-1}&=\dbinom{n}{m}\tag {11}\newline \newline (n-m)\dbinom{n}{m}&=n\dbinom{n-1}{m}\tag {12}\end{align} $$

其中 $n,m\in \mathbb Z$,证明显然。$(11),(12)$ 式被称作吸收公式。

范德蒙德卷积

$$ \sum\limits_i \dbinom{A}{i}\dbinom{B}{C-i}=\dbinom{A+B}{C} \tag{13}$$

其中 $A,B,C\in\mathbb N$,$(13)$ 式被称作范德蒙德卷积。注意它可以简单推广到多元形式。

上指标求和

$$\begin{align} \sum\limits_{i=m}^n \dbinom{i}{m} &= \dbinom{n+1}{m+1} \tag{14} \newline
\sum\limits_{i=0}^n \dbinom{m+i}{i} &= \dbinom{n+m+1}{n} \tag{15} \end{align}$$

其中 $n,m\in\mathbb N$,证明显然。$(14),(15)$ 式被称作上指标求和公式,$(15)$ 式又被称作平行求和公式。

上指标反转

$$\begin{align} \dbinom{n}{m}&=(-1)^m \dbinom{m-n-1}{m} \tag {16}\newline \dbinom{-1}{m}&=(-1)^m\dbinom{m}{m}=(-1)^m \tag {17}\end{align}$$

其中 $n,m\in\mathbb Z$。证明只需要考虑把 $-1$ 的系数均摊到分子下降幂上。$(16)$ 式被称作上指标反转,$(17)$ 式是 $(16)$ 式对于 $n=-1$ 的特殊情况。

$(8)\text{~}(17)$ 式通常被称作组合恒等式。

2.4 二项式反演

形式 I

$$ f(n) = \sum\limits_{k=0}^n (-1)^k\dbinom{n}{k} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^k \dbinom{n}{k} f(k) \tag{18} $$

形式 II

$$ f(n) = \sum\limits_{k=0}^n\dbinom{n}{k} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^{n-k} \dbinom{n}{k} f(k) \tag{19} $$

形式 III

$$ f(n) = \sum\limits_{k=n}^m\dbinom{k}{n} g(k) \Leftrightarrow g(n) = \sum\limits_{k=n}^m (-1)^{k-n} \dbinom{k}{n} f(k) \tag{20} $$

其中 $n,m\in\mathbb N$,$(18),(19),(20)$ 式被称作二项式反演公式。

2.5 第二类 Stirling 数通项

对 $(2)$ 式应用 $(19)$ 式得:

$$ \begin{Bmatrix}n\newline m \end{Bmatrix}m! = \sum\limits_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n \tag{21} $$

其中 $n,m\in\mathbb N$,$(21)$ 式被称为第二类 Stirling 数通项公式。

3 相关题目

「bzoj2839」集合计数
「bzoj3622」已经没有什么好害怕的了
「CF932E」 Team Work
「2018 雅礼集训」方阵
「TJOI / HEOI2016」求和
「LOJ #6716.」 自然数幂之和
「2020联考A卷」组合数问题
「各种数数题」…

作者

ce-amtic

发布于

2020-08-07

更新于

2021-03-23

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×