斯特林数

斯特林数,\(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\)个盒子中,有标号,可以空盒

那么我们枚举选几个盒子,在强行编号即可

应用

上一篇:RLS算法-公式初探


下一篇:Mysql笔记:事务隔离级别理解