§2差分序列與斯特林（Stirling）數

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

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

例如：

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

應用1：S(p,k)是把p個人分進k間無差別的房間

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

a|bcdb|acdc|abdd|abc

ab|cdac|bdad|bc

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

設a(p,k)是p人分進k間相同房間（無空房）的方法數。顯然，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號分別配到k間房的任意一間內,

共有ka(p-1,k)

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

遞推關系和初始條件與第二類斯特林數完全相同！所以a(p,k)=S(p,k)

應用2：k!S(p,k)是把p個人分進k間有差別(如：被標有房號）的房間(無空房）的方法數。

證明：

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

k!S(p,k)

應用3：S(p,k)的表達式：（定理6）

利用容斥原理，還可以stirling數的另一個表達式：證明：

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

U——p人任意分進k間房（可辨）的分法

Ai——

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

應用4：貝爾(bell)數

把p個人分進非空不可辨房間的方法數為

證明：

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

定理7：

證明：

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

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

三、第一類斯特林數1、定義

s(p,0)=0s(p,1)=(p-1)!s(p,p)=1s(p,p-1)=p(p-1)/2兩類斯特林數的比較：2、遞推式kp0123456。。。0010120113023140611615024503510160120274225851517。。。11x2x3x4x5x3、第一類斯特林數的應用

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

設a(p,k)是p人排成k個非空圓圈的方法數。顯然，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)

遞推關系完全與第一類斯特林數相同！a(p,k)=s(p,k)§3

分拆數與Ferrer圖

一、整數的分拆

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

由于求和與順序無關，規定把拆開的數從大到小排列，不再考慮順序。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的一個分拆可以表示為：

分拆數——

把n進行分拆的所有方法數等價于該方程非負整數解的個數。

二、分拆數的母函數例1

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

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

定理1（分拆數的生成函數）

Ferrer圖:

三、Ferrer

圖最大=6的5個數最大=5的6個數

Ferrer圖的共軛性:

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

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

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

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

（插入