在组合数学,Stirling数可指两类数,第一类Stirling数和第二类Stirling数。
stirling常应用于许多组合枚举问题中。
第一类stirling数:
对第一类Stirling数
![](https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D48/sign=99c1bdff8144ebf869716537d8f9ff27/b2de9c82d158ccbf9e2031c61fd8bc3eb03541aa.jpg)
![](https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D43/sign=30abcdfd0c55b31998f9837642a9af65/5ab5c9ea15ce36d34a5102cc3cf33a87e850b1f1.jpg)
![n](http://upload.wikimedia.org/wikipedia/zh/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png)
递推式:
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
性质:
![](https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D77/sign=09ef18017d899e517c8e381343a74595/91529822720e0cf3ebdf85070c46f21fbe09aa26.jpg)
![](https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D79/sign=d5fac2a153fbb2fb302b5a1b4e4a949b/9c16fdfaaf51f3de389b739892eef01f3a297925.jpg)
![](https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D78/sign=29f163dafbfaaf5180e383b78e543aee/43a7d933c895d1434aa12fdf75f082025baf0773.jpg)
![](https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D120/sign=584a2fda0f24ab18e416e53505fbe69a/8718367adab44aed245f7418b51c8701a18bfb3d.jpg)
![](https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D142/sign=d094ab2b30d12f2eca05aa647dc3d5ff/bd3eb13533fa828b0d66571ffb1f4134960a5a81.jpg)
![](https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D168/sign=42ec8ce6d20735fa95f04abfa6530f9f/a8773912b31bb05111ed9dd5307adab44bede006.jpg)
![](https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D248/sign=5ce633be8dd4b31cf43c93bfbfd7276f/b3fb43166d224f4a36af5bee0ff790529822d11c.jpg)
第二类stirling数:
![](https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D51/sign=bd7e0b6dcb11728b342d8c23c9fc647a/1c950a7b02087bf466afd315f4d3572c10dfcf8f.jpg)
![](https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D44/sign=45ffc73c84025aafd7327fcff9ed5ae9/eaf81a4c510fd9f943c6d495232dd42a2934a47d.jpg)
![](https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D243/sign=f515d458a118972ba73a07ced5cd7b9d/b21bb051f8198618137907c840ed2e738bd4e644.jpg)
递推式:
$$\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$