斯特林数,\(OI\)中极其常用的计数利器
依旧是为了自己复习用
第一类斯特林数
\[\begin{bmatrix} n \\ k \end{bmatrix}=s(n,k) \]定义:\(s(n,k)\)表示将\(n\)个元素分成\(k\)个圆排列的方案数
圆排列不同当且仅当形成的排列不能通过旋转得到,\(n\)个元素的圆排列方案为\((n-1)!\)
递推式
那么我们就有了第一类斯特林数的递推方程,\(\mathcal{O(n^2)}\)
\[\begin{bmatrix}0 \\ 0\end{bmatrix} =1 \] \[\begin{bmatrix}n \\ k\end{bmatrix} =\begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + \begin{bmatrix} n-1 \\ k \end{bmatrix} *(n-1) \]也可以写成
\[s(n,k)=s(n-1,k-1)+s(n-1,k)*(n-1) \]可以这样理解,现在我要插入一个数:
1、单独形成一个新的圆排列
2、插入原来的一个圆排列,这样插入的时候原来有\((n-1)\)个数,那就有\((n-1)\)个位置可以选
其他公式
\[\sum _{k=0}^ns(n,k)=n! \]\(n!\)即是全排列的方案数,对应到斯特林数上
一个圆排列相当于是一个置换,那么一个排列一定是由许多个置换组成的
于是我们枚举置换的个数,就是环的个数,因为\(s(n,0)=0\),所以我们把\(0\)也放到了公式中
\[s(n,n-1)=C_n^2 \]这个还是挺显然的,只有一个环中有两个元素,两个元素的圆排列只有\(1\)种,就相当于是组合数
\[s(n,n-2)=2C_n^3+3C_n^4 \]这个和上面那个类似,其实还可以继续往下写,然而没有意义了
\[s(n,2)=(n-1)!*\sum _{i=1}^{n-1}\frac{1}{i} \]这个还不会证
第二类斯特林数
\[\begin{Bmatrix} n \\ k \end{Bmatrix}=S(n,k) \]定义:\(S(n,k)\)表示将\(n\)个元素划分成\(k\)个集合的方案数,集合内无序,集合无编号
递推式
\[\begin{Bmatrix} 0 \\ 0 \end{Bmatrix}=1 \] \[\begin{Bmatrix} n \\ k \end{Bmatrix}=\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}+\begin{Bmatrix} n-1 \\ k \end{Bmatrix}*k \] \[S(n,k)=S(n-1,k-1)+S(n-1,k)*k \]可以理解为插入一个数,要么自己形成一个集合,要么插入到原来的集合
其他公式
\[x^k=\sum_{i=1}^{k}S(k,i)*i!*C_{x}^{i} \]\(x^k\)相当于给你\(k\)个物品放到\(x\)个盒子中,有标号,可以空盒
那么我们枚举选几个盒子,在强行编号即可