Stirling 斯特林数
第一类stirling数
$s(n,k) = \begin{bmatrix} n \\ m \\ \end{bmatrix}$ 表示n个不同元素, 划分成m个非空段(每个非空段 满足循环平移等价) 的方案数
(n个两两不同元素,划分为k个互不区分的非空轮换的方案数, 也就是 如果划分出 [1,2,3] 那么 和[2,3,1]等价和[3,1,2]等价, 但是和[3,2,1]等价
$\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\\ 0\end{bmatrix}=[n=0]$
生成函数
构造生成函数 $F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i$
根据递推公式$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$
有 $F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$