組合數(shù)學(xué)斯特林?jǐn)?shù)

§2差分序列與斯特林（Stirling）數(shù)

一、差分序列1.差分的定義2.差分表01234例1.01234567014916253649135791113…222222…000000…例2.0123456161528456691…5913172125…444444…000000……………3.差分序列的性質(zhì)證明：性質(zhì)1降階效應(yīng)，類似導(dǎo)數(shù)(定理1)證明：由于所以是p-1次多項式，而其他項的次數(shù)至多是p-1性質(zhì)20123456…………類似于泰勒展開，f(x)由x=0點的各階導(dǎo)數(shù)值確定。差分表為012345678900001515357000014102035560013610152128012345678111111111000000000000000000例3解：由于不妨設(shè)因此性質(zhì)3線性（類似導(dǎo)數(shù)）性質(zhì)4（定理2）01234131749…21432…121824666000例4：解：例5解：解：性質(zhì)5（定理3）例601168125662511565175369…1450110194…366084…2424…00…性質(zhì)6

二、第二類斯特林?jǐn)?shù)1、定義比較系數(shù)，知：2、遞推式（定理4）kp0123456701101201130131401761501152510160131906515170163301350140211x2x3x4x5x6證明：n=(n-k)+k3、第二類斯特林?jǐn)?shù)的應(yīng)用

例如：

把a(bǔ),b,c,d4個人分配到2間無差別的房間，不必考慮房間順序，且沒有空房，可行的分配方案為：

應(yīng)用1：S(p,k)是把p個人分進(jìn)k間無差別的房間

(無空房）的方法數(shù)。（定理5）

a|bcdb|acdc|abdd|abc

ab|cdac|bdad|bc

由遞推表可知：S(4,2)=7證明：

設(shè)a(p,k)是p人分進(jìn)k間相同房間（無空房）的方法數(shù)。顯然，a(p,0)=0（不可能做到），

a(p,p)=1（每人一間）。若1號人單占一間：其余p-1人占k-1間——

a(p-1,k-1)

若1號人不單獨占間：先把其余p-1人分進(jìn)排k間房，有a(p-1,k)種方法,

再把1號分別配到k間房的任意一間內(nèi),

共有ka(p-1,k)

根據(jù)加法原理，a(p,k)=a(p-1,k-1)+ka(p-1,k)

遞推關(guān)系和初始條件與第二類斯特林?jǐn)?shù)完全相同！所以a(p,k)=S(p,k)

應(yīng)用2：k!S(p,k)是把p個人分進(jìn)k間有差別(如：被標(biāo)有房號）的房間(無空房）的方法數(shù)。

證明：

S(n,p)是分進(jìn)k間無差別房間，不考慮房間順序。當(dāng)房間有差別時，還要考慮k間房子的排列順序，根據(jù)乘法原理，這樣分房的方法數(shù)為

k!S(p,k)

應(yīng)用3：S(p,k)的表達(dá)式：（定理6）

利用容斥原理，還可以stirling數(shù)的另一個表達(dá)式：證明：

k!S(n,p)是p人分進(jìn)k間有差別房間（非空）方法數(shù)，根據(jù)容斥原理，設(shè)

U——p人任意分進(jìn)k間房（可辨）的分法

Ai——

第i間房是空房的分法（i=1,2,…,k)

應(yīng)用4：貝爾(bell)數(shù)

把p個人分進(jìn)非空不可辨房間的方法數(shù)為

證明：

沒有指定房間數(shù)，但由于房間不空，所以房間數(shù)不超過p。根據(jù)加法定理，推論：把p個人分進(jìn)不超過m間非空不可辨房間的方法數(shù)為

定理7：

證明：

p號人必然被分進(jìn)某一間房。設(shè)p所在的房間還有其他t個人，（t=0,1,2,…,p-1)，只需要把剩下的

p-t-1個人分配房間，

三、第一類斯特林?jǐn)?shù)1、定義

s(p,0)=0s(p,1)=(p-1)!s(p,p)=1s(p,p-1)=p(p-1)/2兩類斯特林?jǐn)?shù)的比較：2、遞推式kp0123456。。。0010120113023140611615024503510160120274225851517。。。11x2x3x4x5x3、第一類斯特林?jǐn)?shù)的應(yīng)用

s(p,k)是把p個人排成k個非空圓圈（循環(huán)排列）的方法數(shù)。證明：

設(shè)a(p,k)是p人排成k個非空圓圈的方法數(shù)。顯然，a(p,0)=0,a(p,p)=1

若1號人單獨排一個圈：其余p-1人排k-1個圈,

有a(p-1,k-1)種方法；若1號人不單獨排一個圈：先把其余p-1人排k個圈，有a(p-1,k)種方法,再把1號分別插入到p-1個人的左邊,

共有（p-1)a(p-1,k)

所以，a(p,k)=a(p-1,k-1)+(p-1)a(p-1,k)

遞推關(guān)系完全與第一類斯特林?jǐn)?shù)相同！a(p,k)=s(p,k)§3

分拆數(shù)與Ferrer圖

一、整數(shù)的分拆

把正整數(shù)n分拆成若干個整數(shù)之和，稱為n的一個分拆。

由于求和與順序無關(guān)，規(guī)定把拆開的數(shù)從大到小排列，不再考慮順序。1：

12：

2,1+13：

3,2+1,1+1+14：

4,3+1,2+2,2+1+1,1+1+1+15：

5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1n的一個分拆可以表示為：

分拆數(shù)——

把n進(jìn)行分拆的所有方法數(shù)等價于該方程非負(fù)整數(shù)解的個數(shù)。

二、分拆數(shù)的母函數(shù)例1

把n分拆成1,2,3之和(可重復(fù))，求其分拆數(shù)的生成函數(shù)。解：n拆成1,2,…,m之和(可重復(fù))，生成函數(shù)是：例2

把n分拆成1,2,3之和，3至少出現(xiàn)1次，求其分拆數(shù)的生成函數(shù)。解：n拆分出的最大數(shù)=m，其生成函數(shù)是：

定理1（分拆數(shù)的生成函數(shù)）

Ferrer圖:

三、Ferrer

圖最大=6的5個數(shù)最大=5的6個數(shù)

Ferrer圖的共軛性:

三、分拆數(shù)的組合應(yīng)用（1）把n分拆成“最大為m”的分拆數(shù)，也是把n分拆成“m個數(shù)之和”的分拆數(shù)，等價于：

把n個相同的球放入m個相同的非空盒子的方法數(shù)。（2）把n分拆成“最大數(shù)不超過m”的分拆數(shù)，也是把n分拆成“至多m個數(shù)之和”的分拆數(shù)，等價于：

把n個相同的球放入m個相同的盒子（盒可以空）的方法數(shù)。

四、分球問題序號球標(biāo)號？房標(biāo)號？房可空?方法數(shù)000×××n拆成“恰好m個數(shù)”的分拆數(shù)001××√n拆成“至多m個數(shù)”的分拆數(shù)010×√×

（插入