5整數(shù)拆分與指數(shù)型母函數(shù)

1《圖論與組合優(yōu)化》第六講

整數(shù)的拆分指數(shù)型母函數(shù)2第五講:

內(nèi)容提要I.整數(shù)拆分與Ferrers圖像

III.差分表介紹*II.指數(shù)型母函數(shù)

3I.整數(shù)拆分與Ferrers圖像1.整數(shù)的拆分

所謂整數(shù)拆分即把正整數(shù)n分解成若干正整數(shù)n1,n2,…,nk的和

n=n1+n2+…+nk.

例如,整數(shù)5可拆分成:

5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+14如果考慮次序,就是有序拆分;否則就是無序拆分.一般所說拆分都指無序的拆分.即在n的拆分中要求n1≥n2≥…≥

nk≥1n的兩個拆分n1≥n2≥…≥

nk≥1,

m1≥m2≥…≥ml≥1只有滿足k=l與而且ni=mi的時候,才認為兩個拆分相同.n的不同無序拆分總數(shù)記為p(n)或pn.可以利用字典序方法給所有拆分排序.5用P(n,m)表示自然數(shù)n表示成m個正整數(shù)之和的個數(shù)，則用P’(n,m)表示自然數(shù)n表示成m個有序正整數(shù)之和的個數(shù),P’(n)為n的有序拆分總數(shù)，則P’(n,m)=C(n-1,m-1)62.整數(shù)拆分的組合解釋相當于把n個無區(qū)別的球放到n個無標志的盒子,盒子允許空著,也允許放一個以上球.拆分數(shù)p(n)這是一個非常有用的組合數(shù),但是它的精確表達式很難得到.可以利用母函數(shù),求出給定n的拆分數(shù).也可以利用母函數(shù)估計p(n)的值或給出上界:73.與整數(shù)拆分有關的問題無重復砝碼稱重問題:

若有1克、2克、3克、4克的砝碼各一枚,問能稱出哪幾種重量？每種重量有幾種稱法方案？解釋結(jié)果,說明問題對應何種整數(shù)分拆.8(2)可有限重復砝碼稱重問題:

若有1克的砝碼3枚,2克的4枚,4克的2枚.問能稱出哪些重量？各有幾種方案？解釋結(jié)果,說明問題對應何種整數(shù)分拆.9(3)可無限重復砝碼稱重問題:

求用1角,2角,3角的郵票可帖出的不同數(shù)值的方案數(shù).解釋結(jié)果,說明問題對應何種整數(shù)分拆.101112(4)有限制的整數(shù)拆分問題:

整數(shù)n拆分成1,2,3,…,m的和,并允許重復,求其母函數(shù)G1(x).

如果其中m至少出現(xiàn)一次,其母函數(shù)G2(x)如何？13解釋結(jié)果重復次數(shù)不限制但最大數(shù)有限制144.整數(shù)拆分數(shù)列p(n)的母函數(shù)G(x):為何不容易得到p(n)的精確表達式?當n給定之后情況如何?利用分析方法可以得到上界.155.Ferrers圖象與整數(shù)分拆性質(zhì)(1)整數(shù)分拆的圖象表示:

假定n拆分成

n=n1+n2+…+nk,n1≥n2≥…≥nk≥

1.可建立一個正方形格子圖表示該拆分:格子按行左對齊第1行n1個格子,第2行n2個格子,……,第k行nk個格子.如圖5.1所示.16即上層的格子數(shù)不少于下層的格子數(shù)目,這樣的格子圖形稱為Ferrers圖象.圖5.117(2)Ferrers圖象具有如下性質(zhì)：每一層至少有一個格子.如果對圖象沿主對角線進行轉(zhuǎn)置,即把第1行變?yōu)榈?列互換,第2行變?yōu)榈?列互換,…,則所得仍然是Ferrers圖象.這兩個Ferrers圖象稱為是一對共軛的Ferrers圖象.

圖5.1共軛圖象為圖5.218利用Ferrers圖象可得到整數(shù)拆分的十分有趣的結(jié)果.圖5.219(3)整數(shù)分拆性質(zhì):整數(shù)n拆分成最大數(shù)為k的拆分數(shù)與把數(shù)n拆分成k個數(shù)的和的拆分數(shù)相等.

整數(shù)n拆分成最多不超過m個數(shù)的拆分數(shù)與最大的數(shù)不超過m的拆分數(shù)相等.

整數(shù)n拆分成互不相同的若干奇數(shù)的和的拆分數(shù),與把n拆分成有自共軛的Ferrers圖象的拆分數(shù)相等.

正整數(shù)n拆分成不超過k個數(shù)的和的拆分數(shù),等于將n+k拆分成正好k個數(shù)的拆分數(shù).這些性質(zhì)很容易用Ferrers圖象方法證明.20II.指數(shù)型母函數(shù)一般母函數(shù)是用基函數(shù){1,x,x2,…}來定義的.這種母函數(shù)對于組合類型的數(shù)列的研

究很有用.但是,對研究排列類型的數(shù)列用起來很不方便.排列類型數(shù)列是用基函數(shù){1,x,x2/2!,…}來定義,這樣使用起來更方便一些.基本思想并沒有變,只是選擇了新的基.21基函數(shù)正好是出現(xiàn)在函數(shù)ex的冪級數(shù)展開式中的函數(shù):設有數(shù)列a0,a1,a2,…，則稱下列函數(shù)為

該數(shù)列的指數(shù)型母函數(shù):22常用公式23(a)

設n=n1+n2+…+nk.

若元素a1有n1個,

元素a2有n2個,…,元素ak有nk個,則由

這n個元素組成的不同的排列總數(shù)為(b)設n=n1+n2+…+nk.若元素a1有n1個,元素a2有n2個,…,元素ak有nk個,由這n個元素中取r個排列數(shù)為pr,則序列p0,

p1,…,pn的指數(shù)型母函數(shù)為:24

試給出這個指數(shù)型母函數(shù)的組合意義.

比如xk/k!項的組合含義是什么?

試給出pr的精確表達式.25例1

若有8個元素,其中設a1重復3次，a2重復2次,a3重復3次.從中取r個元素的排列數(shù)pr,則序列p0,p1,p2,…,p8的指數(shù)型母函數(shù)為:如何得出pr?例如：p4=4!×(35/12)=70.26例2

由1，2，3，4，5五個數(shù)字組成的n位數(shù)，求其中4，5出現(xiàn)偶數(shù)次，1，2，3出現(xiàn)次數(shù)不限的數(shù)的個數(shù)an。解：{an}的指數(shù)型母函數(shù)為27例3

r個編號自1至r的球分放進4個有標志盒子里，第1盒只能放奇數(shù)個，第2盒只能放偶數(shù)個，第3、4盒可放的球數(shù)不限，求放法種數(shù)ar.解：{ar}的指數(shù)型母函數(shù)為28例5.3由1，2，3，4，5五個數(shù)字組成的n位數(shù)，求其中4，5出現(xiàn)偶數(shù)次，1，2，3出現(xiàn)次數(shù)不限的數(shù)的個數(shù)an。國考考題29解：{an}的指數(shù)型母函數(shù)為30例4

確定用紅、綠、藍三色對1×n棋盤的方格進行染色的方案數(shù)an,并且使得綠色的方格數(shù)為偶數(shù).

解約定a0=1.顯然

an為三種顏色組成的n階排列,每種顏色的重復數(shù)沒有限制,但是綠色在排列中必須出現(xiàn)偶數(shù)次.這樣{an}的指數(shù)型母函數(shù)為3132III.差分表方法*

假定P(x)是非負整數(shù)集N0上的函數(shù).用下列方式得到一個數(shù)表稱為P(x)的差分表:

第1行:P(x),x=0,1,2,…

第2行:ΔP(x)=P(x+1)-P(x),x=0,1,2,………

第k行:Δk

P(x)=Δk-1P(x+1)-Δk-1P(x),

x=0,1,2,………

函數(shù)Δk

P(x)稱為函數(shù)P(x)的k階差分.P(x)稱為0階差分.33定理

設ΔrP(x)是P(x)的r階差分，則差分表：P(0)P(1)P(2)P(3)P(4)P(5)……ΔP(0)

ΔP(1)

ΔP(2)

ΔP(3)

ΔP(4)……Δ2P(0)

Δ2P(1)

Δ2P(2)

Δ2P(3)……Δ3P(0)

Δ3P(1)

Δ3P(2)……Δ4P(0)Δ4P(1)……34

例如P(n)=2n2+3n+1的差分表如下:161528456691…5913172125…44444…0000…000…

如果一個差分表中有一行全為零,則

相繼的行也必然為零,因此就沒有必

要再寫下去了.差分表的特點：每一行的元素是它上一行的

(右肩-左肩)35如果P(x)=anxn+an-1xn-1+…+a1x+a0,其

中an≠0,則P(x)的n+1階差分恒為0.注意到每取一次差分,非常數(shù)多項式次數(shù)就降低一次,而常數(shù)差分恒為0.差分表最大特點是由左邊第一斜列可以決定整個差分表及其多項式本身:

161528456691…5913172125…

44444…

0000…36如果多項式P(x)差分表的左斜列的元素為b0,b1,…,bn,0,0,…,則

P(x)=b0C(x,0)+b1C(x,1)+…+bnC(x,n)

其中C(x,k)=x(x-1)…(x-k+1)/k!利用上述公式可以得到一個很有用處的公式:37011681256625…11565175369…1450110194…366084…2424…0

下面給出差分方法的兩個應用例5.6

求14+24+…+m4的和,m為正整數(shù).解

令P(x)=x4,則P(x)的差分表為38

根據(jù)剛才得到的公式:

用類似的方法,對任何正整數(shù)n和m都

可以計算1n+2n+…+mn.

在數(shù)值計算中差分方法還有其他重要應用