Stirling數

维基百科，自由的百科全书

在組合數學，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)$ ：

{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
{C},{A,D,B}
{D},{A,B,C}
{D},{A,C,B}

這可以用有向圖來表示。

給定 $s (n,0) = 0, s (1,1) = 1$ ，有遞歸關係 $s(n+1,k)=s(n,k-1) - 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組，可以是甲乙一組、丙丁一組，或甲丙一組、乙丁一組，或甲丁一組、乙丙一組，或其中三人同一組另一人獨立一組，即是：

{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
{C},{A,B,D}
{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)$
$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)$