Wenchong Huang

旧博客，文章搬迁完后删除

第一类斯特林数表示的是将n个不同元素排列成k个不同的环的方案数（可以通过旋转得到的两个环视为相同的环），记作： $\begin{bmatrix}n\\ k\end{bmatrix}$

读作：n轮换k

定义 $\begin{bmatrix} 0\\ 0 \end{bmatrix} =1, \begin{bmatrix} n\\ 0 \end{bmatrix} =0(n>0)$

它不像组合数一样有直接计算公式，而是只能通过递推得到。其递推公式为：

$\begin{bmatrix} n\\ k \end{bmatrix} = \begin{bmatrix} n-1\\ k-1 \end{bmatrix} +(n-1) \begin{bmatrix} n-1\\ k \end{bmatrix}$

$\begin{bmatrix} n\\ 1 \end{bmatrix} =(n-1)!$
$\begin{bmatrix} n\\ n-1 \end{bmatrix} =C_n^2$
$\sum_{k=0}^n\begin{bmatrix} n\\ k \end{bmatrix} =n!$
不知道它跟斯特林数有什么关系，但做到了这个题，题解说是什么斯特林公式： $n!\approx \sqrt{2\pi n}\left ( \frac{n}{e} \right )^n$

第二类斯特林数表示的是将n个不同元素划分成k个子集的方案数，记作： $\begin{Bmatrix} n\\ k \end{Bmatrix}$

读作：n子集k

定义 $\begin{Bmatrix} 0\\ 0 \end{Bmatrix} =1, \begin{Bmatrix} n\\ 0 \end{Bmatrix} =0(n>0)$

同样的，它只能通过递推得到。其递推公式为：

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

$\begin{Bmatrix} n\\ n \end{Bmatrix} =1$
$\begin{Bmatrix} n\\ 2 \end{Bmatrix} =2^{n-1}+1$
$\begin{Bmatrix} n\\ n-1 \end{Bmatrix} = \begin{Bmatrix} n\\ n-1 \end{Bmatrix} +\begin{Bmatrix}n\\n-1\end{Bmatrix}=C_n^2$
$x^k=\sum_{i=1}^k\begin{Bmatrix} k\\ i \end{Bmatrix} i!C_x^i$
设 $z=n-\left \lceil \frac{k+1}{2} \right \rceil, w=\left \lfloor \frac{k-1}{2} \right \rfloor$ ，则有 $\begin{Bmatrix} n\\ k \end{Bmatrix} =C_z^w(mod 2)$

就这样吧。这个公式啊，真的是糟糕透顶