在组合数学,Stirling数可指两类数,第一类Stirling数和第二类Stirling数。
stirling常应用于许多组合枚举问题中。
第一类stirling数:
对第一类Stirling数
递推式:
s(p,k)的递推公式: $s(p,k)=(p-1) \times s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1$
边界条件:s(p,0)=0 ,p>=1 s(p,p)=1 ,p>=0
性质:
第二类stirling数:
递推式:
$$\begin{Bmatrix} n \\ k \end{Bmatrix}=\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}+\begin{Bmatrix} n-1 \\ k \end{Bmatrix}*k$$
S(p,k)的递推公式是:$S(p,k)=k \times S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1$$
边界条件:S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1
通项递推式:
$S(n,m)=\frac{1}{m!} \sum _{k=0}^m (-1)^kC_m^k(m-k)^n$
性质:
- $s(0,0)=1$;
- $S(n,0)=0,n>0$
- $S(n,n)=1$
- $S(n,2)=S(n-1,1)+S(n-1,2)*2=1+S(n-1,2)*2=2^{n-1}-1$
- $S(n,n-1)=C_n^2$
- $S(n,n-2)=C_n^3+3C_n^4$
简单巧妙的证明:我们分成两种情况,把nn个不同的元素分成n−2n−2个集合有两种情况,分别是有一个集合有三个元素和有两个集合有两个元素。对于前者,我们选出三个元素为一个集合,其他的各成一个集合,这种情况的方案数就是C3nCn3。对于后者,先选出四个元素来,考虑怎么分配。当其中一个元素选定另一个元素形成同一个集合时,这种情况就确定了,所以是3C4n3Cn4。加法原理计算和即得证。
-
$S(n,3)=\frac{1}{2}(3^{n-1}+1)-2^{n-1}$
- $S(n,n-3)=C_n^4+10C_n^5+15C_n^6$