【Concrete Mathematics】(Special Number抄書筆記)Stirling Numbers(1)

04-24

tip：標題是第一部分的意思，這是個容易引起歧義的寫法。

那我們就先來介紹第二類stirling numbers

$1.1$ 組合意義（Combinatorial meaning）:

第二類stirling numbers通常由兩個有序數對 $(n,k)$ 組成，表示的意義是把n個互不相同的元素分配到k個非空集合中的方案數，通常記作 $left{ egin{matrix} n\ k end{matrix} ight}$ ，當 $n=4,k=2$ 的時候，分配方案如下： $left{1,2,3 ight}cup left{4 ight}$ , $left{1,2,4 ight}cup left{3 ight}$ , $left{1,3,4 ight}cup left{2 ight}$ , $left{2,3,4 ight}cup left{1 ight}$ , $left{1,2 ight}cup left{3,4 ight}$ , $left{1,3 ight}cup left{2,4 ight}$ , $left{1,4 ight}cup left{2,3 ight}$

所以 $left{ egin{matrix} 4\ 2 end{matrix} ight}= 7$

$1.2$ 特殊值(special numbers):

比較顯然的，當你只有一個集合的時候，你n個數都要放進這一個集合中，這時也只有這一種分配方案，因此 $left{ egin{matrix} n\ 1 end{matrix} ight}=1(n>0)$ ,注意到當n=0的時候，0個元素不可能分配到使1個集合非空，因此 $left{ egin{matrix} 0\ 1 end{matrix} ight}=0$ ，事實上，在 $n < k$ 的情況下，根據鴿巢原理可知必定會存在一個集合為空，所以是不可能符合分配方案的，因此 $left{ egin{matrix} n\ k end{matrix} ight}=0(n<k)$

當你擁有兩個集合的時候，你又該怎樣分配呢？試想你把 $n$ 個元素上方用數字 $0:1$ 標上表示去哪個集合，那麼隨意標記的方案數就是 $n$ 位二進位數的方案數 $2^n$ 種，注意到有兩種情況是不行的，就是全為0或全為1的情況，所以剩下的方案數為 $2^n-2$ 種，你還會發現集合0和集合1在放元素的時候是等價的，也就是說對於這個 $n$ 位的二進位數取反是無意義的，試想你把所有集合0的數放到集合1中，同時把所有集合1的數放到集合0中，因為集合本身是無序的，所以這兩種方案視作一種方案，且在 $2^n-2$ 種方案中一一對應，因此真正有效的方案數為 $2^{n-1}-1$ 種。因此 $left{ egin{matrix} n\ 2 end{matrix} ight}=2^{n-1}-1(n>0)$

$1.3$ 遞推式(recurrence)

考慮組合意義，給你 $n$ 個元素把它們放到 $k$ 個非空集合中，對於第 $n$ 個元素，我們有兩种放法：

第一种放法是先將 $n-1$ 個元素放到 $k-1$ 個集合裡面去，而因為要保證集合非空，第 $n$ 個元素就只能放到第 $k$ 個集合裡面去，這部分有 $left{ egin{matrix} n-1\ k-1 end{matrix} ight}$ 種方案；

第二种放法是先將 $n-1$ 個元素放到 $k$ 個集合裡面去，因為現在集合都是非空的，因此我們可以隨意地將第n個元素放到k個集合的任意一種方案，因此這部分有 $k imesleft{ egin{matrix} n-1\ k end{matrix} ight}$ 種方案。

因此我們得到遞推式： $left{ egin{matrix} n\ k end{matrix} ight}= kleft{ egin{matrix} n-1\ k end{matrix} ight} + left{ egin{matrix} n-1\ k-1 end{matrix} ight}(n>0)$

現在我們開始講第一類stirling numbers

$2.1$ 組合意義（Combinatorial meaning）:

第一類stirling numbers的定義與第二類極為相似，唯一不同的一處是將分為 $k$ 個集合改為了分為 $k$ 個圓排列，定義便是將n個元素分為k個圓排列的方案數，記作 $left[ egin{matrix} n\ k end{matrix} ight]$ 。讀者現在可能還不會太清楚它們的具體區別，因此這裡我們舉個例子，還是 $n=4,k=2$ 的時候，分配方案如下

$[1,2,3][4]$ , $[1,3,2][4]$

$[1,2,4][3]$ , $[1,4,2][3]$

$[1,3,4][2]$ , $[1,4,3][2]$

$[2,3,4][1]$ , $[2,4,3][1]$

$[1,2][3,4]$ , $[1,3][2,4]$ , $[1,4][2,3]$

因此 $left[ egin{matrix} 4\ 2 end{matrix} ight]=11$

容易發現，上面的列舉方案中第一列和最後一行與剛剛的第二類stirling numbers是一模一樣的，不同的地方在於第二列的前四個方案，其實都是在第一列的前四個方案的基礎上將三個元素的圓排列再進行排列罷了，而當元素個數為 $1,2$ 個的時候，圓排列數=1（如果你熟悉圓排列數，你肯定容易發現n個元素的圓排列數 $=(n-1):!$ ）。因此我們容易發現 $left[ egin{matrix} n\ k end{matrix} ight] geq$ $left{ egin{matrix} n\ k end{matrix} ight}$

$2.2$ 特殊值(special numbers):

根據鴿巢原理，我們發現當 $n =k$ 的時候一個非空圓排列的元素至多不超過1個， $n=k+1$ 的時候一個非空圓排列的元素至多不超過2個，而1,2的圓排列數都為1，也就是說當一個圓排列元素只有1,2的時候，它的方案數和同元素個數的集合一樣都是1，也就是說此時第一類stirling數和第二類stirling數在方案上等價。即 $left[ egin{matrix} n\ n end{matrix} ight]=left{ egin{matrix} n\ n end{matrix} ight}$ , $left[ egin{matrix} n\ n-1 end{matrix} ight]=left{ egin{matrix} n\ n-1 end{matrix} ight}$

易得： $left[ egin{matrix} n\ n end{matrix} ight]=left{ egin{matrix} n\ n end{matrix} ight}=1$

對於 $left{ egin{matrix} n\ n-1 end{matrix} ight}$ ，我們可以發現這樣分配的時候僅會出現一個有兩個元素的集合，而隨著分配方案的不同，這個兩個元素的集合的方案一定是不同的（想一想為什麼（其它單個元素的集合是等價的）），因此我們有 $left[ egin{matrix} n\ n-1 end{matrix} ight]=left{ egin{matrix} n\ n-1 end{matrix} ight}=left( egin{matrix} n\ 2end{matrix} ight)=left( egin{matrix} n\ n-1end{matrix} ight)$

$2.3$ 遞推式(recurrence)

與推導第二類stirling numbers時的方法一樣，我們有兩種分配方案：

一種是先將 $n-1$ 個元素放到 $k-1$ 個非空圓排列裡面去，因為要保證圓排列非空，第 $n$ 個元素就只能放到第 $k$ 個圓排列裡面，方案數為 $left[ egin{matrix} n-1\ k-1 end{matrix} ight]$

另一種是將 $n-1$ 個元素放到 $k$ 個非空圓排列裡面去，對於第 $n$ 個元素，我們可以任意放到k個圓排列里的一個中去，而對於一個擁有 $k_i$ 個元素的圓排列，將第n個元素的放進去的方案數也有 $k_i$ 種，而 $sum_i k_i=n-1$ ，因此我們將第 $n$ 個元素放進一組 $k$ 個非空圓排列的方案數為 $n-1$ ，而這樣的k個非空圓排列有 $left[ egin{matrix} n-1\ k end{matrix} ight]$ 組，根據乘法原理，這種分配方法的方案數為 $(n-1)left[ egin{matrix} n-1\ k end{matrix} ight]$

因此我們得到遞推式：

$left[ egin{matrix} n\ k end{matrix} ight]= (n-1)left[ egin{matrix} n-1\ kend{matrix} ight] + left[ egin{matrix} n-1\ k-1 end{matrix} ight](n>0)$

$2.4$ 多說一句(in addition)

第一類stirling數的定義和置換群有著相似之處（圓排列， $n$ 個元素分成 $k$ 份），那麼我們可以很容易知道，對於一個 $n$ 個元素的置換群，它如果有 $k$ 個循環節，那麼方案數即為第一類stirling數。

本文為蒟蒻所作，若有語言欠妥之處，請在評論區指出，謝謝。

若要轉載請註明出處。