斯特林数

——James Stirling

第一类Stirling数

定义

• 第一类Stirling数表示表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目
• $s_u(n,m)$ 表示无符号第一类Stirling数，$s_s(n,m)$ 表示有符号第一类Stirling数

$$x^{n\uparrow}=x(x+1)(x+2)\cdots(x+n-1)=\sum\limits_{k=0}^{n}s_u(n,k)x^k \\ x^{n\downarrow}=x(x-1)(x-2)\cdots(x-n+1)=\sum\limits_{k=0}^{n}s_s(n,k)x^k$$

递推式

$$s_u(n,m)=s_u(n-1,m-1)+n\cdot s_u(n-1,m) \\ s_s(n,m)=s_s(n-1,m-1)-n\cdot s_s(n-1,m)$$

性质

$$s_u(n,n-1)=\binom{n}{2}$$

$n$ 个不同的元素构成 $n-1$ 个圆排列，相当于选取 $2$ 个元素放在同一个圆排列里。

$$s_u(n,2)=(n-1)!\sum\limits_{i=1}^{n-1}\frac{1}{i}$$

考虑第一类斯特林数的定义，第 $n$ 个元素可以放到前 $n-1$ 个元素的左边，也可以单独新开一个圆排列。

$(n-1)!\sum\limits_{i=1}^{n-1}\frac{1}{i}=\sum\limits_{i=1}^{n-1}\frac{(n-1)!}{i}=2 \times 3 \times \cdots \times (n-1) + 1 \times 3 \times \cdots \times (n-1) + \cdots + 1 \times 2 \times \cdots \times (n-2)$

可以看出，多项式的第 $i$ 项把乘 $i$ 变成了乘 $1$，相当于先把第 $1$ 个元素放入一个圆排列中，剩下的 $n-1$ 个元素，第 $i$ 个元素有 $i$ 种选择，因为它可以从前 $i$ 个元素中任选一个放到它的左边，当 $i$ 种选择变成 $1$ 种选择时，是用它作为第一个元素来开辟另一个圆排列。

$$n!=\sum\limits_{k=0}^{n}s_u(n,k)$$

利用置换群的思想，每一个排列都有几个置换环，$k$ 表示环的个数，由于 $S(n,0)=0$，所以 $k$ 可以从 $0$ 开始。

$$s_s(n,m)=(-1)^{n+m}s_u(n,m)$$

证明略。

$$0^n=\sum\limits_{k=0}^{n}s_s(n,k)\ (n \neq 1)$$

注意 $0^0=1$。

考虑当 $n=2$ 时，有 $1/2$ 和 $12$ 两种方案，其中 “/” 分隔不同的圆排列，这时奇数个圆排列的个数和偶数个圆排列的个数是相同的；后面每新来一个元素，都是在原来的基础上扩展，比如新来一个元素 $3$，那么有 $13/2$ 和 $132$，$1/23$ 和 $123$，$1/2/3$ 和 $12/3$，可以看出在 $1/2$ 的某个位置上插入一个元素，$12$ 的对应位置上也可以插入这个元素，这就保证了奇数个圆排列的个数和偶数个圆排列的个数永远相同。

pascal三角形

n	$s_u(n,m)$	$s_s(n,m)$
0	1	1
1	0 1	0 1
2	0 1 1	0 -1 1
3	0 2 3 1	0 2 -3 1
4	0 6 11 6 1	0 -6 11 -6 1
5	0 24 50 35 10 1	0 24 -50 35 -10 1
6	0 120 274 225 85 15 1	0 -120 274 -225 85 -15 1
7	0 720 1764 1624 735 175 21 1	0 720 -1764 1624 -735 175 -21 1

第二类Stirling数

定义

• 第二类Stirling数表示表示将 $n$ 个不同元素拆分成 $m$ 个集合的方案数
• 记为 $S(n,m)$

递推式

$$S(n,m)=S(n−1,m−1) + m \cdot S(n−1,m)$$

通项公式

$$S(n,m)=\frac{1}{m!} \sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n$$

容斥原理。其中 $k$ 表示空集的个数，$(m-k)^n$ 表示每个元素都有 $m-k$ 种选择，除以 $m!$ 是因为每个集合是相同的。

我们继续对这个式子进行变形：

$$\begin{eqnarray}S(n,m) &=&\frac{1}{m!}\sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n\\ &=&\frac{1}{m!}\sum\limits_{k=0}^{m}(-1)^k\frac{m!}{k!(m-k)!}(m-k)^n\\ &=&\sum\limits_{k=0}^{m}\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!} \end{eqnarray}$$

然后就可以不预处理组合数，而是通过FFT/NTT求解。

推论

$$m!=\sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^m$$

因为 $S(m,m)=1$，即 $\dfrac{1}{m!} \sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^m=1$，所以 $\sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^m=m!$。

性质

$$S(n,2)=2^{n-1}-1$$

相当于先把其中一个元素放到一个集合，然后其他 $n-1$ 个元素每个元素都有 $2$ 种选择，最后再减掉全部放入一个集合的情况。

$$\begin{eqnarray}m^n &=&\sum\limits_{k=0}^{m}A(m,k) \cdot S(n,k)\\ &=&\sum\limits_{k=0}^{m}k! \cdot\binom{m}{k} \cdot S(n,k) \end{eqnarray}$$

$m^n$ 表示将 $n$ 个不同的元素放入 $m$ 个不同的集合的方案数，允许有空集；$k$ 表示非空集合的个数。

pascal三角形

n	S(n,m)
0	1
1	0 1 1
3	0 1 3 1
4	0 1 7 6 1
5	0 1 15 25 10 1
6	0 1 31 90 65 15 1
7	0 1 63 301 350 140 21 1
8	0 1 127 966 1701 1050 266 28 1
9	0 1 255 3025 7770 6951 2646 462 36 1

两类Stirling数之间的关系

Ⅰ.

$$S(n,0)=0^n=\sum\limits_{k=0}^{n}s_s(n,k)\ (n \neq 1)$$

Ⅱ.

$$S(n,n-1)=\binom{n}{2}=s_u(n,n-1)$$

Ⅲ.

$$\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^n=n!=\sum\limits_{k=0}^{n}s_u(n,k)$$

Ⅳ.

$$\sum\limits_{k=0}^{n}S(n,k)s(k,m)=\sum\limits_{k=0}^{n}s(n,k)S(k,m)$$

类似于矩阵的对称转置关系（证明待填坑）。