斯特林数的基本概念

thkkkAK了!

  • 第一类Stirling

    第一类Stirling数($ [^n_m] $)表示表示将$n$个不同元素构成$m$个圆排列的数目。

    第一类Stirling数分为有符号($s_s$)和无符号($s_u$)

    • 递推式

      有符号:$s_s(n+1,m)=s_s(n,m-1)-n\dot~s_s(n,m)$

      无符号:$s_u(n+1,m)=s_u(n,m-1)+n\dot~s_u(n,m)$

    • 性质

      • 有符号
        1. $s_s(n,m)=(-1)^{n+m}s_u(n,m)$
        2. $(\sum_{k=0}^ns_s(n,k))=[n=0]$
      • 无符号
        1. $s_u(0,0)=1$
        2. $s_u(n,0)=0$
        3. $s_u(n,n)=1$
        4. $s_u(n,1)=(n-1)!$
        5. $s_u(n,n-1)=C_n^2$
        6. $s_u(n,2)=(n-1)!\dot~\sum_{i=1}^{n-1}\dfrac1i$
        7. $s_u(n,n-2)=2\dot~C^3_n+3\dot~C^4_n$
        8. $\sum_{k=0}^ns_u(n,k)=n!$
  • 第二类Stirling

    第二类Stirling数($\left\{^n_m\right\}$、$S(n,m)$)实际上是集合的一个拆分,表示将$n$个不同的元素拆分成$m$个集合的方案数

    描述为:将$n$个不同的球放入$m$个无差别的盒子中,要求盒子非空,有几种方案?

    • 递推式

      $S(n+1,m)=S(n,m-1)+m\dot~S(n,m)$

    • 性质

      1. $S(n,0)=[n=0]$

      2. $S(n,1)=1$

      3. $S(n,n)=1$

      4. $S(n,2)=2^{n-1}-1$

      5. $S(n,n-1)=C_n^2$

      6. $S(n,n-2)=C_n^3+3\dot~C_n^4$

      7. $S(n,3)=\dfrac{3^{n-1}+1}2-2^{n-1}$

      8. $S(n,n-3)=C_n^4+10\dot~C_n^5+15_n^6$