斯特林數

"]給出把整數 n ]給出把整數 n 設S(p

斯特林數出現在許多組合枚舉問題中. 對第一類斯特林數 StirlingS1[n,m]， 給出恰包含 m 個圈的 n 個元素 的排列數目. 斯特林數滿足母函式關係 . 注意某些 的定義與 Mathematica 中的不同，差別在於因子 . 第二類斯特林數 StirlingS2[n,m]給出把 n 個可區分小球分配到m個不可區分的的盒子，且盒子沒有空盒子的方法的數量. 它們滿足關係 . 劃分函式 PartitionsP[n]給出把整數 n 寫為正整數的和，不考慮順序的方法的數目. PartitionsQ[n]給出把整數 n 寫為正整數的和，並且和中的整數是互不相同的 寫法的數目
設S(p,k)是斯特林數
S(p,k)的一個組合學解釋是：將p個物體劃分成k個非空的不可辨別的（可以理解為盒子沒有編號）集合的方法數。
S(p,k)的遞推公式是：
　S(p,k) = k*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
遞推關係的說明：考慮第p個物品，p可以單獨構成一個非空集合，此時前p-1個物品構成k-1個非空的不可辨別的集合，方法數為S(p-1,k-1)；也可以前p-1種物品構成k個非空的不可辨別的集合，第p個物品放入任意一個中，這樣有k*S(p-1,k)種方法。
第一類斯特林數和第二類斯特林數有相同的初始條件，但遞推關係不同。引用Brualdi《組合數學》里的一段注釋“對於熟悉線性代數的讀者，解釋如下：具有（比如）實係數，最多為p次的那些各項式形成一個p+1維的向量空間。組1，n，n^2，...。n^p和組A(n, 0)，A(n,1)，A(n,2)，... ，A(n,p)都是該空間的基。第一類Stirling數和第二類Stirling數告訴我們如何用其中的一組基表示另一組基。”