斯特林数 | 王大神—

Markdown

发布日期: 2021-12-31

更新日期: 2021-12-31

文章字数: 2.4k

阅读次数:

第一类斯特林数

定义：将 $n$ 个元素，换份为 $k$ 个圆排列的方案数，记作 $s(n,k)$，或 $\big[_k^n\big]$。又根据正负性分为无符号的 $s_u(n,m)$ 和带符号的 $s_s(n,m)$。组合数学中的第一类斯特林数一般是只无符号的。

圆排列

可以看成旋转置换，通过旋转任意角度排列仍然相同，就属于一种方案。

第一类斯特林数就是解决圆排列的方案数。

递推求第一类斯特林数

将 $1$ 到 $n$ 的排列划分为 $k$ 个圆排列，共有多少种方案？

一共有两种放置方法：$n$ 新圆中，或放到已经有的圆中。

$n$ 放到一个新圆中

假设前 $n-1$ 个数放到 $k-1$ 个圆中，$n$ 放到新圆 $k$ 中，此时的方案数和不放当前数的方案数相同，即：$\big[_{k-1}^{n-1}\big]$。

$n$ 放到已有的圆中

那么有 $n-1$ 数，放到 $k$ 个圆里，就有 $(n-1)\times \big[_{k}^{n-1}\big]$ 种放置方案（有 $n-1$ 条边，放在每条边上都算一种方案）。

将两种情况统计起来，就得到了递推式：

$\big[_{k}^{n}\big]=\big[_{k-1}^{n-1}\big]+(n-1)\times \big[_{k}^{n-1}\big]$

其中 $s(n,n)=1(n\ge 0),s(n,0)=0(n\ge 1)$

第一类斯特林数表

    0    1    2    3    4    5    6
1   1
2   0    1
3   0    1    1
4   0    6   11    6    1
5   0   24   50   35   10    1
6   0  120  274  225   85   15    1

斯特林三角

有符号斯特林数和无符号斯特林数的关系：

$s(n,k)=(-1)^{n-k}\big[_{k}^{n}\big]$

     无符号斯特林数            有符号斯特林数

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

第一类斯特林数的性质

$s_u(0,0)=1$

~~人为规定~~

$s_u(n,0)=0$
$s_u(n,n)=1$
$s_u(n,1)=(n-1)!$
$s_u(n,n-1)=C_n^2$
$s_u(n,n-2)=2\times C^3_n+3\times C^4_n$
$s_u(n,2)=(n-1)!\sum_{i=1}^{n-1}{\frac{1}{i}}$

如果 $n$ 个数放在 $1$ 个圈里，有 $(n-1) !$ 种情况，现在选 $i$ 个数放到第二个圈中：

$\frac{C^i_n\times (i-1)!\times (n-i-1)!}{A_2^2}$

注意两个圈是没有区别的。

$=\frac{1}{2}\times \frac{n!}{i!(n-i)!}\times (i-1)!\times (n-i-1)!$ $=\frac{1}{2}\times \frac{n!}{i(n-i)}$ $=\frac{1}{2}\times (n-1)!\times \frac{n}{i(n-i)}$ $=\frac{1}{2}\times (n-1)!\times (\frac{1}{i}+\frac{1}{n-i})$

方案总数（就是将上面的 $i$ 枚举出来）：

$\sum_{i=1}^{n-1}{\frac{C^i_n\times (i-1)!\times (n-i-1)!}{2}}$ $=\sum_{i=1}^{n-1}{\frac{1}{2}{\times (n-1)!\times (\frac{1}{i}+\frac{1}{n-i})}}$ $\because \sum_{i=1}^{n-1}{\frac{1}{i}}=\sum_{i=1}^{n-1}{\frac{1}{n-i}}$ $\therefore =\sum_{i=1}^{n-1}{\frac{1}{2}\times(n-1)!\times 2\times \frac{1}{i}}$ $=\sum_{i=1}^{n-1}(n-1)!\times \frac{1}{i}$ $=(n-1)!\times \sum_{i=1}^{n-1}{\frac{1}{i}}$

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

上升幂&下降幂

上升阶乘幂（上升幂）

$x^{\overline{n}}=\prod_{k=0}^{n-1}{(x+k)=x(x+1)(x+2)…(x+n-1)}$

上升幂转化为普通幂

$x^{\overline{n}}=\sum_{k=0}^n{\begin{gathered} \begin{bmatrix} n\\k \end{bmatrix} \end{gathered}}x^k$

普通幂转化为上升幂

$x^n= \sum_{k}{ \begin{gathered} \begin{Bmatrix} n\\k \end{Bmatrix} \end{gathered} }(-1)^{n-k}x^{\overline{k}}$

（大括号是第二类斯特林数，后面会讲。）

下降阶乘幂（下降幂）

$x^{\underline{n}}=\frac{x!}{(x-n)!}=\prod_{k=0}^{n-1}{(n-k)}$

普通幂转换为下降幂：

$x^n={\sum_{k}{ \begin{gathered} \begin{Bmatrix} n\\k \end{Bmatrix} \end{gathered} }x^{\underline{k}}}$

下降幂转化为普通幂：

$x^{\underline{n}}=\sum_{k}{ \begin{gathered} \begin{bmatrix} n\\k \end{bmatrix} \end{gathered} (-1)^{n-k}x^k }$

多项式下降阶乘幂表示与多项式点值表示的关系

多项式的下降幂阶乘幂表示就是用

$f(x)=\sum_{i=0}^{n}{b_ix^{\underline{i}}}$

的形式表示一个多项式，而点值表示就是用 $n+1$ 个点

$(i,a_i),i=0…n$

来表示一个多项式。

那么就有：

$a_k=\sum_{i=0}^n{b_ik^{\underline{i}}}$ $a_k=\sum_{i=0}^n{\frac{b_ik!}{(k-i)!}}$ $\frac{a_k}{k!}=\sum_{i=0}^k{b_i\frac{1}{(k-i)!}}$

这是一个卷积的形式，那么我们可以用 FFT 来优化。

第一类斯特林数的生成函数

有符号斯特林数的生成函数是下降幂：

$x^{\underline{n}}=\sum_{k=0}^n{s_s(n,k)x^k}$

无符号斯特林数的生成函数是上升幂：

$x^{\overline{n}}=\sum_{k=0}^{n}{s_u(n,k)x^k}$

第二类斯特林数

将 $n$ 个不同的元素拆分成 $m$ 个集合间有序（集合有编号，且不能空）的方案数，记 $S(n,m)$ 或者

$\begin{gathered} \begin{Bmatrix} n\\m \end{Bmatrix} \end{gathered}$

和第一类斯特林数不同的是，这里的集合内部是不考虑次序的，而圆排列圆内部是有序的。典型的例子：将 $n$ 和不同的球放入 $m$ 个无差别的盒子中，要求盒子非空，有几种方案？

$S(n,m)=\frac{1}{m!}\sum_{k=0}^m{(-1)^kC^k_m(m-k)^n}$

递推求第二类斯特林数

将 $n$ 个元素分成 $k$ 个集合，我们来分析第 $n$ 个数 $n$，有哪些放置方法。

有两种情况：$n$ 放在一个新的集合中，或者 $n$ 放在已有的集合中。

$n$ 放在一个新的集合中

假设前 $n-1$ 和数放到 $k-1$ 个集合中，$n$ 放到自己的集合中，就是第 $k$ 个集合。方案数和不放这个元素的方案数相等：

$\begin{gathered} \begin{Bmatrix} n-1\\k-1 \end{Bmatrix} \end{gathered}$

$n$ 放到已有的集合中

前 $n-1$ 个数放到 $k$ 个集合里，第 $n$ 个数放到前 $k$ 个集合里，对于每一个集合中，由于内部是无序的，所以有 $k$ 中选择，

$k\times \begin{gathered} \begin{Bmatrix} n-1\\k \end{Bmatrix} \end{gathered}$

综合上面两种情况，有递推公式：

$\begin{gathered} \begin{Bmatrix} n\\k \end{Bmatrix} \end{gathered} = \begin{gathered} \begin{Bmatrix} n-1\\k-1 \end{Bmatrix} \end{gathered} +k\times \begin{gathered} \begin{Bmatrix} n-1\\k \end{Bmatrix} \end{gathered}$

同时有 $S(n,n)=1,p\ge 0$，$S(n,0)=0,n\ge 1$。

第二类斯特林数三角

0                1
1               0 1
2              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

第二类斯特林数性质

$S(n,0)=0^n$
$S(n-1)=1$
$S(n,n)=1$
$S(n,2)=2^{n-1}-1$
$S(n,n-1)=C(n,2)$
$S(n,n-2)=C(n,3)+3\times C(n,4)$
$S(n,3)=\frac{1}{2}(3^{n-1}+1)-2^{n-1}$
$S(n,n-3)=C(n,4)+10\times C(n,5)+15\times C(n,6)$
$\sum_{k=0}^n{S(n,k)=B_n}$

$B_n$ 是贝尔数。

$\sum_{k=0}^{m}{(-1)^kC^k_m(m-k)^m}=m!$
$n^k=\sum_{i=0}^k{S(k,i)\times i!\times C^i_n}$

第二类斯特林数生成函数

$G_0(S(n,k))=\sum_{n\ge k}{S(n,k)x^n}=\frac{x^k}{(1-x)(1-2x)…(1-kx)}=\frac{x^k}{\prod_{r=1}^k{(1-rx)}}$

指数生成函数：

$G_2(S(n,k))=\sum_{n\ge k}{S(n,k)}\times \frac{x^n}{n!}=\frac{(e^x-1)^k}{k!}$

第二类斯特林数的通项公式

$\begin{gathered} \begin{Bmatrix} n\\m \end{Bmatrix} \end{gathered} =\sum_{i=0}^m{\frac{(-1)^{m-i}i^n}{i!(m-i)!}}$

第三类斯特林数（拉赫数）

无符号拉赫数：

升阶函数：

$x^{\overline{n}}=\sum_{k=0}^n{L(n,k)x^{\underline{k}}}$

降阶函数：

$x^{\underline{n}}=\sum_{k=0}^n{(-1)^{n-k}L(n,k)x^{\overline{k}}}$

其中 $L(n,k)$ 为拉赫数。

有符号拉赫数：

升阶函数：

$x^{\overline{n}}=(-1)^n\sum_{k=0}^n{L(n,k)x^{\underline{k}}}$

降阶函数：

$x^{\underline{n}}=\sum_{k=0}^n{(-1)^{k}L(n,k)x^{\overline{k}}}$

无符号拉赫数计算的是有 $n$ 个元素的集合拆分成 $k$ 个非空线性有序子集方法的数目。

无符号拉赫数公式：

$L(n,k)=C_{n-1}^{k-1}\frac{n!}{k!}$

有符号拉赫数公式：

$L^{'}(n,k)=(-1)^nC_{n-1}^{k-1}\frac{n!}{k!}$

递推求第三类斯特林数

无符号：

$L(n,k+1)=\frac{n-k}{k(k+1)}L(n,k)$

和：

$L(n+1,k)=(n+k)L(n,k)+L(n,k-1)$

有：$L(n,0)=0$，$L(n,k)=0(k > n )$，$L(1,1)=1$。

第三类斯特林数表

     0     1     2     3     4     5     6
0    1
1    0     1
2    0     2     1
3    0     6     6     1
4    0    24    36    12     1
5    0   120   240   120    20     1
6    0   720  1800  1200   300    30     1

第三类斯特林数的性质

$L(0,0)=1,L(n,0)=0(n>0)$
$k>n,L(n,k)=0$
$L(n,1)=n!$
$L(n,2)=\frac{(n-1)n!}{2}$
$L(n,3)=\frac{(n-2)(n-1)n!}{12}$
$L(n,n-1)=n(n-1)$
$L(n,n)=1$
$\sum_{n\ge k}{L(n,k)\frac{x^n}{n!}}=\frac{1}{k!}(\frac{x}{1-x})^k$

无符号拉赫数还有：

$L(n,k)=C_{n-1}^{k-1}\frac{n!}{k!}=C_n^k\frac{(n-1)!}{(k-1)!}=C_n^kC_{n-1}^{k-1}(n-k)!$
$L(n,k)=\frac{n!(n-1)!}{k!(k-1)!}\times \frac{1}{(n-k)!}=(\frac{n!}{k!})^2\frac{k}{n(n-k)!}$

无符号拉赫数还可写成：

$L(n,k)=\sum_{j=0}^n{ \begin{gathered} \begin{bmatrix} n\\j \end{bmatrix} \end{gathered} \begin{gathered} \begin{Bmatrix} j\\k \end{Bmatrix} \end{gathered} }$

还有：

$\sum_{j\ge 0}{L(n,j)L(j,k)}=\delta_{nk}$

$\delta_{nk}$ 是克罗内克尔 $\delta$。