第二類斯特林數

一、第二類斯特林數怎麼用

第二類斯特林數是關於集合劃分的一個數學函數。其定義為將n個標有編號的球放到k個無標號的盒子里，且每個盒子至少有一個球的劃分數目。

第二類斯特林數在很多概率和組合問題中都有應用。例如，將n個物品劃分為k組，將n個球放入k個箱子中，等等。

在Python中，可以使用SymPy模塊的stirling函數來計算第二類斯特林數。stirling函數在SymPy中的輸入形式為stirling(n, k)。其中n和k都是整數，表示將n個球劃分到k個盒子中。

from sympy import *
n = 5
k = 3
stirling(n, k)

輸出結果為6，表示將5個標號的球劃分到3個無標號的盒子中，共有6種劃分方式。

二、第二類斯特林數通項公式推導

第二類斯特林數的通項公式可以通過生成函數方法得到。生成函數是一種將序列轉化為代數函數的方式。若對於序列an，將其轉化為其生成函數A(x)，則A(x)的第n項係數即為an。

設F(x)為球的生成函數，G(x)為盒子的生成函數，則有

F(x) = (e^x – 1)^n

G(x) = e^(kx)

因為對於每一種劃分，其方案數等於球的劃分方式個數與盒子的混排方式個數的乘積。而盒子的混排方式個數為k!，所以第二類斯特林數的生成函數為

S_n^k = n*G(x)/k!)

上式中[x^n]表示A(x)中x的n次冪係數。

三、第二類斯特林數有單峰嗎

一般來說，第二類斯特林數沒有單峰性質。單峰是指函數的值隨著參數的增加先增加後減小。而對於第二類斯特林數，其函數值不具有單峰性質。

以n=5為例，將5個標號為1~5的球劃分到3個無標號的盒子中，共有第二類斯特林數S_5^3=25種劃分方式。這些劃分方式的數量分別為1、4、6、7、6、1。可以發現，這些數量的分布不具有單峰性質。

四、第二類斯特林數卷積形式

第二類斯特林數的卷積形式為

S_n^k = 1/k! * Σ(j=0 ~ k) (-1)^(k-j) * C(k, j) * j^n

其中C(k, j)表示從k個無標號的盒子中選擇j個盒子的組合數。上式中每一項分別對應將n個球劃分到j個盒子中，再將(k-j)個盒子中的每個盒子再劃分成任意的若干個盒子。因此，上式的每一項都是一個劃分方式數目的和。

五、第二類斯特林數遞推公式

第二類斯特林數的遞推公式為

S_n^k = S_{n-1}^{k-1} + k * S_{n-1}^k

該公式的意思是將第n個球分配到k個盒子中可以分成兩種情況。第一種情況是將這個球單獨分到一個新的盒子中，此時有S_{n-1}^{k-1}種劃分方式。第二種情況是將球放到已有的k個盒子中的某一個盒子中，此時有k * S_{n-1}^k種劃分方式。

六、第二類斯特林數分塊

第二類斯特林數的分塊表示法可以理解為將n個球劃分為m個子集的方案數。對於給定的n和m，其分塊數目為B(n, m)。

第二類斯特林數的分塊數目可以通過一個遞推公式進行計算。該遞推公式如下：

B(n+1, m) = m * B(n, m) + B(n, m-1)

上式的含義是將n+1個標號的球劃分成m個非空子集，可以分成兩種情況。第一種情況是將這個球單獨作為一個新的子集，此時數量為m * B(n, m)。第二種情況是將這個球放到已有的m個子集中的某一個子集中，此時數量為B(n, m-1)。

七、第二類斯特林數通項公式

第二類斯特林數還可以使用常數係數矩陣的形式表示。其通項公式為

S_n^k = 1/k! * Σ(j=0 ~ k) (-1)^(k-j) * C(k, j) * j^n

上式中C(k, j)表示從k個無標號的盒子中選擇j個盒子的組合數。上式的求和項中每一項分別對應將n個球劃分到j個盒子中，再將(k-j)個盒子中的每個盒子再劃分成1~n個盒子的總劃分方式數。

八、第二類斯特林數求和公式

第二類斯特林數的求和公式為

Σ(k=0 ~ n) S_n^k = n!

該公式表示將n個標號為1~n的球劃分到任意個無標號的盒子中的劃分方式數之和等於n!。

九、第二類斯特林數性質

第二類斯特林數具有很多重要的性質。

1. 對於所有的n，有S_n^n=1。

2. 對於所有的n，有S_n^1=1。

3. 連續的第二類斯特林數之和有一個遞推公式：S_n^1 + S_n^2 + … + S_n^n = B_n，其中B_n為n的貝爾數。

4. 第二類斯特林數滿足遞推公式S_n^k = S_{n-1}^{k-1} + k * S_{n-1}^k。

5. 第二類斯特林數滿足性質：

S_n^k = Σ(j=0 ~ k) (-1)^(k-j) * C(k, j) * j^n

該性質表明第二類斯特林數可以表示為k次冪的線性組合。

6. 第二類斯特林數可以用循環展開式表示：

S_n^k = (-1)^k * Σ(j=0 ~ k) (-1)^j * k^j * Binomial(k, j) * (k-j)^n

上式中Binomial(k, j)表示從k個元素中選取j個元素的組合數。