斯特灵数

维基百科,自由的百科全书
跳转至: 导航搜索

在組合數學,Stirling數可指兩類數,都是由18世紀數學家James Stirling提出的。

第一類[编辑]

s(4,2)=11

第一類Stirling數是有正負的,其絕對值是n個元素的項目分作k個環排列的方法數目。常用的表示方法有s(n,k) , \left[\begin{matrix} n \\ k \end{matrix}\right]

換個較生活化的說法,就是有n個人分成k組,每組內再按特定順序圍圈的分組方法的數目。例如s(4,2)

  1. {A,B},{C,D}
  2. {A,C},{B,D}
  3. {A,D},{B,C}
  4. {A},{B,C,D}
  5. {A},{B,D,C}
  6. {B},{A,C,D}
  7. {B},{A,D,C}
  8. {C},{A,B,D}
  9. {C},{A,D,B}
  10. {D},{A,B,C}
  11. {D},{A,C,B}

這可以用有向圖來表示。

  • 給定s(n,0)=0,s(1,1)=1,有遞歸關係s(n+1,k)=s(n,k-1) + n \; s(n,k)

递推关系的说明:考虑第n+1个物品,n+1可以单独构成一个非空循环排列,这样前n种物品构成k-1个非空循环排列,方法数为s(n,k-1);也可以前n种物品构成k个非空循环排列,而第n+1个物品插入第i个物品的左边,这有n*s(n,k)种方法。


  • | s(n,1) | =(n-1)!
  • s(n,k) = (-1)^{n+k} | s(n,k) |
  • s(n,n-1) = - C(n,2)
  • s(n,2) = (-1)^n (n-1)!\; H_{n-1}
  • s(n,3) = \frac{1}{2} (-1)^{n-1} (n-1)! [ (H_{n-1})^2 - H_{n-1}^{(2)} ]

H_n^{(m)}調和數的推廣。

s(n,k)是遞降階乘多項式的係數:

x^{\underline{n}}= x(x-1)(x-2)\ldots(x-n+1) = \sum_{k=1}^n s(n,k)x^k

第二類[编辑]

第二類Stirling數是n個元素的集定義k個等價類的方法數目。常用的表示方法有S(n,k) , S_n^{(k)} ,  \left\{\begin{matrix} n \\ k \end{matrix}\right\}

換個較生活化的說法,就是有n個人分成k組的分組方法的數目。例如有甲、乙、丙、丁四人,若所有人分成1組,只有所有人在同一組這個方法,因此S(4,1)=1;若所有人分成4組,只可以人人獨立一組,因此S(4,4)=1;若分成2組,可以是甲乙一組、丙丁一組,或甲丙一組、乙丁一組,或甲丁一組、乙丙一組,或其中三人同一組另一人獨立一組,即是:

  1. {A,B},{C,D}
  2. {A,C},{B,D}
  3. {A,D},{B,C}
  4. {A},{B,C,D}
  5. {B},{A,C,D}
  6. {C},{A,B,D}
  7. {D},{A,B,C}

因此S(4,2)=7


  • 給定S(n,n)=S(n,1)=1,有遞歸關係S(n,k) = S(n-1,k-1) + k S(n-1,k)
  • 递推关系的说明:考虑第n个物品,n可以单独构成一个非空集合,此时前n-1个物品构成k-1个非空的不可辨别的集合, 方法数为S(n-1,k-1);也可以前n-1种物品构成k个非空的不可辨别的 集合,第n个物品放入任意一个中,这样有k*S(n-1,k)种方法。
  • S(n,n-1)=C(n,2)=n(n-1)/2
  • S(n,2)=2^{n-1} - 1
  • S(n,k) =\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j} C(k,j) j^n
  • B_n=\sum_{k=1}^n S(n,k)

C(k,j)是二項式係數,B_n是貝爾數

兩者關係[编辑]

\sum_{n=0}^{\max\{j,k \}} S(n,j) s(k,n) = \sum_{n=0}^{\max\{j,k \}} s(n,j) S(k,n) = \delta_{jk}

\delta_{jk}克羅內克爾δ