斯特林数（Stirling Number）
斯特林数主要处理的是把\(N\)个不同的元素分成\(k\)个集合或环的个数问题
1.第二类斯特林数
表示将\(n\)个元素划分成\(m\)个集合，每个集合非空的方案数，读作\(n\)子集\(m\)，记作\(\begin{Bmatrix}n\\\\m \end{Bmatrix}\),又称为斯特林子集数
1.1、组合意义推导
新来一个元素\(n\)，对于该元素我们有两种方案：
（1）：元素\(n\)单独做一个集合，故此时的方案为：\(\begin{Bmatrix}n-1\\\\k-1\end{Bmatrix}\)
（2）：元素\(n\)放入一个现有的非空集合，那么我们需要选择一个非空集合，故此时的方案为:\(C_k^1\begin{Bmatrix}n-1\\\\k\end{Bmatrix}\)
所以通过加法原理可以得到：\(\begin{Bmatrix}n\\\\m \end{Bmatrix}=\begin{Bmatrix}n-1\\\\k-1\end{Bmatrix}+C_k^1\begin{Bmatrix}n-1\\\\k\end{Bmatrix}\)
1.2、容斥原理推导
$$ 设全集S={乱放}\\ 子集A_i={第i个盒子是空的}\\
\[\begin{aligned} \therefore|S-U_{k=0}^{m}A_i|&=\sum_{k=0}^{m}(-1)^k[子问题:哪几个盒子是空的]\\ &=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC_m^k(m-k)^n\\ &=\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!} \end{aligned}\] \ 通项公式 \[\begin{Bmatrix} n\\\\m \end{Bmatrix}\]=_{k=0}^m $$
通过观察我们可以发现通项公式其实是一个卷积的形式，因此我们可以利用FFT在\(O(nlogn)\)的时间内求对于\(n\)不变，任意\(m\in[0,n]\)的\(\begin{Bmatrix}n\\\\m\end{Bmatrix}\)
1.3、生成函数推导
\[ 由于分的每个集合是没有标号的，故可以写出每个集合的指数生成函数A(x)=\sum_{i=1}^{+\infty}\frac{x^i}{i!}\\ \therefore \begin{Bmatrix} n\\m \end{Bmatrix}=\frac{[x^n]A^m(x)}{m!} \]
那么可以利用多项式快速幂求出
通过观察我们还可以发现，在\(m\)不变时，利用多项式快速幂求出\(A^m(x)\)后，对于任意\(n>m\)都可以通过\(A^m(x)\)在\(O(1)\)时间内知道对应的\([x^n]\)
1.4、第二类斯特林数的重要性质
\[ n^k=\sum_{i=0}^{k}i!C_n^i\begin{Bmatrix}k\\i\end{Bmatrix} \]
1.4.1、理解
等式左边考虑\(k\)个球可以放置在\(n\)个盒子里
等式右边考虑为枚举非空盒子的数量\(i\),那么把\(k\)个球放到\(i\)个盒子
1.4.2、运用
可以将一个高次方数转化为第二类斯特林数
1.5、第二类斯特林数其他性质
\[ \begin{aligned} &\begin{Bmatrix} 0\\0 \end{Bmatrix}=1\\ &\begin{Bmatrix} n\\0 \end{Bmatrix}=0,n>0 \\ &\begin{Bmatrix} n\\n \end{Bmatrix}=1 \\ &\begin{Bmatrix} n\\2 \end{Bmatrix}=\begin{Bmatrix} n-1\\1 \end{Bmatrix}+2\times \begin{Bmatrix} n-1\\2 \end{Bmatrix}=1+2^{n-1} \\ &\begin{Bmatrix} n\\n-1 \end{Bmatrix}=C_n^2 \\ &\begin{Bmatrix} n\\n-2 \end{Bmatrix}=C_n^3+3C_n^4 \\ &\begin{Bmatrix} n\\3 \end{Bmatrix}=\frac{1}{2}(3^{n-1}+1)-2^{n-1} \\ &\begin{Bmatrix} n\\n-3 \end{Bmatrix}=C_n^4+10C_n^5+15C_n^6 \end{aligned} \]
2、第一类斯特林数
表示 \(n\) 个数形成 \(m\) 个环的方案数，读作\(n\) 轮换\(m\) ,记作\(\begin{bmatrix}n\\\\m\end{bmatrix}\)，又称为斯特林轮换数
2.1、组合意义推导
新来一个元素\(n\)，对于该元素我们有两种方案：
（1）：元素\(n\)单独做一个环，故此时的方案为：\(\begin{bmatrix}n-1\\\\k-1\end{bmatrix}\)
（2）：元素\(n\)放入一个现有的环，那么我们需要选择一个数，并把这个新数插到其前面，故此时的方案为:\(C_{n-1}^1\begin{bmatrix}n-1\\\\k\end{bmatrix}\)
所以通过加法原理可以得到：\(\begin{bmatrix}n\\\\m \end{bmatrix}=\begin{bmatrix}n-1\\\\k-1\end{bmatrix}+C_{n-1}^1\begin{bmatrix}n-1\\\\k\end{bmatrix}\)
2.2、生成函数推导
\[ 同样地我们考虑单个环上的生成函数，对于长度为i的环而言，其方案数为(i-1)!\\ \therefore 我们可以写出单个环的指数生成函数:A(x)=\sum_{i=1}^{n}(i-1)!\frac{x^i}{i!}=\sum_{i=1}^{n}\frac{x^i}{i}\\ \therefore \begin{bmatrix} n\\m \end{bmatrix}={[x^n]A^m(x)} \]
2.3、第一类斯特林数的性质
\[ \begin{aligned} &\begin{bmatrix} 0\\0 \end{bmatrix}=1 \\ &\begin{bmatrix} n\\0 \end{bmatrix}=0,n>0 \\ &\begin{bmatrix} n\\1 \end{bmatrix}=(n-1)! \\ &\begin{bmatrix} n\\n-1 \end{bmatrix}=C_n^2 \\ &\begin{bmatrix} n\\n-2 \end{bmatrix}=(n-1)!\times \sum_{i=1}^{n-1}\frac{1}{i} \\ &\begin{bmatrix} n\\n-2 \end{bmatrix}=2C_n^3+3C_n^4 \\ &\sum_{k=0}^{n}\begin{bmatrix} n\\k \end{bmatrix}=n! \end{aligned} \]
