組合數(shù)學(xué)（第二版）PPT完整全套教學(xué)課件

目錄第一章組合數(shù)學(xué)基礎(chǔ)第二章母函數(shù)及其應(yīng)用第三章遞推關(guān)系第四章容斥原理第五章抽屜原理和瑞姆賽(Ramsey)理論第六章波利亞(Pólya)定理第一章組合數(shù)學(xué)基礎(chǔ)1.1緒論1.2兩個基本法則1.3排列與組合1.4組合等式及其組合意義1.5多項式系數(shù)1.6排列的生成算法1.7組合的生成算法1.8應(yīng)用舉例1.9斯特靈(Stirling)近似公式

1.1緒論組合數(shù)學(xué)起源于數(shù)學(xué)游戲.例如幻方問題:給定自然數(shù)1,2,…,n2,將其排列成n階方陣,要求每行、每列和每條對角線上n個數(shù)字之和都相等.這樣的n階方陣稱為n階幻方.每一行(或列、或?qū)蔷€)之和稱為幻和.圖1.1.1是一個3階幻方,其幻和等于15.首先,人們要問:(1)存在性問題:即n階幻方是否存在?(2)計數(shù)問題:如果存在,對某個確定的n,這樣的幻方有多少種?(3)構(gòu)造問題:即枚舉問題,亦即如何構(gòu)造n階幻方?圖1.1.13階幻方

【例1.1.1】36名軍官問題:有1,2,3,4,5,6共六個團隊,從每個團隊中分別選出具有A、B、C、D、E、F6種軍銜的軍官各一名,共36名軍官.問能否把這些軍官排成6×6的方陣,使每行及每列的6名軍官均來自不同的團隊且具有不同軍銜.

本問題的答案是否定的

【例1.1.2】用3種顏色紅(r)、黃(y)、藍(b)涂染平面正方形的四個頂點,若某種染色方案在正方形旋轉(zhuǎn)某個角度后,與另一個方案重合,則認(rèn)為這兩個方案是相同的.例如,對圖1.1.2的涂染方案(a),當(dāng)正方形逆時針旋轉(zhuǎn)90°時就變?yōu)榉桨?b),因此,在正方形可旋轉(zhuǎn)的前提下,這兩種方案實質(zhì)上是一種方案.那么,我們要問:不同的染色方案共有多少種?

染色方案的存在性是不可爭議的,而且可知共有34=81種方案,問題是要計算不同的染色方案,顯然屬于計數(shù)問題.后面將會看到,在旋轉(zhuǎn)條件下,不同的染色方案總數(shù)為圖1.1.2正方形的頂點染色

【例1.1.3】不同身高的26個人隨意排成一行,那么,總能從中挑出6個人,讓其出列后,他們的身高必然是由低到高或由高到低排列的.

計算機科學(xué)中涉及的算法大致可分為兩類.第一類是計算方法,它主要解決數(shù)值計算問題,如方程求根、解方程組、求積分等,其數(shù)學(xué)基礎(chǔ)是高等數(shù)學(xué)與線性代數(shù).第二類是組合算法,它解決搜索、排序、組合優(yōu)化等問題,其數(shù)學(xué)基礎(chǔ)就是組合數(shù)學(xué).

按所研究問題的類型,組合數(shù)學(xué)所研究的內(nèi)容可劃分為:組合計數(shù)理論、組合設(shè)計、組合矩陣論和組合優(yōu)化.本書將以組合計數(shù)理論為主,部分涉及其它內(nèi)容

組合學(xué)問題求解的方法大致可以分為兩類.一類是從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)法,例如,利用容斥原理、二項式定理、波利亞(Pólya)定理解計數(shù)問題;解遞推關(guān)系的特征根方法、母函數(shù)方法;解存在性問題的抽屜原理等.另一類方法則不同,它們通常與問題所涉及的組合學(xué)概念無關(guān),而對多種問題均可使用.常用的有:

(1)數(shù)學(xué)歸納法.本方法大家都已熟悉,這里不再講述.

(2)迭代法.例如已知數(shù)列{hn}滿足關(guān)系

求hn的解析表達式.

直接迭代即得

(3)一一對應(yīng)技術(shù).這是組合數(shù)學(xué)理論常用的一個計數(shù)技巧.其原理就是建立兩個事物之間的一一對應(yīng)關(guān)系,把一個較復(fù)雜的組合計數(shù)問題A轉(zhuǎn)化成另一個容易計數(shù)的問題B,從而利用對B的計數(shù)運算達到對A的各種不同方案的計數(shù).它的應(yīng)用是多方面的,在組合學(xué)中最常見的是利用它將問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式.

(4)殊途同歸方法.即從不同角度討論計數(shù)問題,以建立組合等式,尤其是在組合恒等式的證明中,故也稱組合意義法.

(5)數(shù)論方法.特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進行分析推理的方法.本書用的較多的是方法(3)與(4).下面先給出一一對應(yīng)技術(shù)的兩個實例,以體會該方法的巧妙之處.

【例1.1.4】有100名選手參加羽毛球比賽,如果采用單循環(huán)淘汰制,問最終產(chǎn)生冠軍共需要進行多少場比賽.

解因為采用的是單循環(huán)淘汰制,所以每兩名選手比賽產(chǎn)生一個失敗者,且每個失敗者只能失敗一次.因此,失敗的人數(shù)與比賽場數(shù)之間一一對應(yīng),計算比賽場數(shù)問題轉(zhuǎn)化為計算失敗人數(shù)問題.后者的解顯然是99人,故應(yīng)該比賽99場

【例1.1.5】設(shè)某地的街道將城市分割成矩形方格,某人在其住處A(0,0)的向東7個街道、向北5個街道的大廈B(7,5)處工作(見圖1.1.3),按照最短路徑(即只能向東或向北走),他每次上班必須經(jīng)過某12個街道,問共有多少種不同的上班路線.圖1.1.3最短路徑

1.2兩個基本法則1.2.1加法法則

加法法則如果完成一件事情有兩個方案,而第一個方案有m種方法,第二個方案有n種方法可以實現(xiàn),只要選擇任何方案中的某一種方法,就可以完成這件事情,并且這些方法兩兩互不相同,則完成這件事情共有m+n種方法。

若用集合語言,加法法則可以描述為:設(shè)有限集合A有m個元素,B有n個元素,且A與B不相交,則A與B的并共有m+n個元素.

也可以從概率論角度描述為:設(shè)事件A有m種產(chǎn)生方式,事件B有n種產(chǎn)生方式,則事件“A或B”有m+n種產(chǎn)生方式.當(dāng)然,A與B各自所含的基本事件是互相不同的.

【例1.2.1】某班有男生18人,女生12人,從中選出一名代表參加會議,問共有多少種選法.

解用集合A表示男生,B表示女生,則該班中的學(xué)生要么屬于A,要么屬于B.根據(jù)加法法則,全班共有18+12=30個學(xué)生,故有30種選法.

【例1.2.2】用一個小寫英文字母或一個阿拉伯?dāng)?shù)字給一批機器編號,問總共可能編出多少種號碼.

解英文字母共有26個,數(shù)字0~9共10個,由加法法則,總共可以編出26+10=36個號碼.

1.2.2乘法法則

乘法法則如果完成一件事情需要兩個步驟,而第一步有m種方法、第二步有n種方法去實現(xiàn),則完成該件事情共有m·n種方法.

乘法法則也可以用集合語言描述為:設(shè)有限集合A有m個元素,B有n個元素,a∈A,b∈B,記(a,b)為一有序?qū)?所有有序?qū)?gòu)成的集合稱為A和B的積集(或笛卡兒乘積),記作A×B.那么,A×B共有m·n個元素.

同理,讀者不難從概率論角度理解乘法法則

【例1.2.3】仍設(shè)某班有男生18人,女生12人,現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽,共有多少種選法?

解仍像例1.2.1那樣,用集合A表示男生,B表示女生,那么,根據(jù)乘法法則,共有18×12=216種選法.

【例1.2.4】給程序模塊命名,需要用3個字符,其中首字符要求用字母A~G或U~Z,后兩個要求用數(shù)字1~9,問最多可以給多少種程序命名.

解首先,由加法法則,首字符共有7+6=13種選法.其次,再由乘法法則,最多可以產(chǎn)生13×9×9=1053個不同的名稱.

【例1.2.5】從A地到B地有n1條不同的道路,從A地到C地有n2條不同的道路,從B地到D地有m1條不同的道路,從C地到D地有m2條不同的道路,那么,從A地經(jīng)B或C到達目的地D共有多少種不同的走法?

解首先,由乘法法則,從A地經(jīng)B到達D地共有n1×m1種走法,由A經(jīng)C到達D共有n2×m2種走法,再由加法法則知,從A地經(jīng)B或C到達D地共有n1m1+n2m2種不同的走法.

1.3排列與組合

1.3.1相異元素不允許重復(fù)的排列數(shù)和組合數(shù)

眾所周知,從n個相異元素中不重復(fù)地取r個元素的排列數(shù)和組合數(shù)分別為:

相異元素不允許重復(fù)的排列問題也可以描述為:

將r個有區(qū)別的球放入n個不同的盒子,每盒不超過一個,則總的放法數(shù)為P(n,r).同樣,若球不加區(qū)別,則有C(n,r)種放法.這就是排列與組合的數(shù)學(xué)模型———分配問題,也稱為分配模型.

1.3.2相異元素允許重復(fù)的排列

從n個不同元素中允許重復(fù)地選r個元素的排列,簡稱r元重復(fù)排列.其排列的個數(shù)記為RP(∞,r).其對應(yīng)的分配模型是將r個有區(qū)別的球放入n個不同的盒子,每個盒子中的球數(shù)不加限制而且同盒的球不分次序.

顯然,這樣的排列數(shù)RP(∞,r)=nr.

從集合的角度理解,問題也可以描述為:設(shè)集合S={∞·e1,∞·e2,…,∞·en},即S中共含有n類元素,每個元素有無窮多個,從S中取r個元素的排列數(shù)即為RP(∞,r).

1.3.3不盡相異元素的排列

設(shè)S={n1·e1,n2·e2,…,nt·et},即元素ei有ni個(i=1,2,…,t),且n1+n2

+…+nt=n,從S中任取r個元素,求其排列數(shù)RP(n,r).

本問題的數(shù)學(xué)模型是將r個有區(qū)別的球放入t個不同的盒子,而每個盒子的容量是有限的,其中第i個盒子最多只能放入ni

個球,求分配方案數(shù).

相對于前兩種情況而言,此處講的是有限重復(fù)的排列問題,即相異元素不重復(fù)的排列強調(diào)的是不重復(fù),即盒子的容量為1;允許重復(fù)的排列實際上針對的是無限重復(fù),即盒子的容量無限.二者都是極端的情況.而有限重復(fù)問題恰好介于兩者之間,即盒子的容量有限.

此問題的計算比較復(fù)雜,將在2.3節(jié)詳細討論.這里只給出幾個特例:

(1)當(dāng)r=1時,RP(n,1)=P1t=t.

(2)當(dāng)r=n時,此n個元素的全排列數(shù)為

(3)當(dāng)t=2時,

1.3.4相異元素不允許重復(fù)的圓排列

【例1.3.1】把n個有標(biāo)號的珠子排成一個圓圈,共有多少種不同的排法?

解這是典型的圓排列問題.對于圍成圓圈的n個元素,同時按同一方向旋轉(zhuǎn),即每個元素都向左(或向右)轉(zhuǎn)動一個位置,雖然元素的絕對位置發(fā)生了變化,但相對位置未變,即元素間的相鄰關(guān)系未變,這樣的圓排列認(rèn)為是同一種,否則便是不同的圓排列.下面從兩種角度推導(dǎo)圓排列數(shù)的計算公式

方法一先令n個相異元素任意排成一行(稱為線排列),共有n!種排法,再將其首尾相接圍成一圓,當(dāng)圓轉(zhuǎn)動一個角度時,對應(yīng)另一個線排列,當(dāng)每個元素又轉(zhuǎn)回到原先的位置時,相當(dāng)于n個不同的線排列,故圓排列數(shù)為

方法二先取出某一元素k,放于圓上某確定位置,再令余下的n-1個元素作成一個線排列,首尾置于k的兩側(cè)構(gòu)成一個圓排列同樣可得到CP(n,n)=(n-1)!.

【例1.3.2】從n個相異元素中不重復(fù)地取r個圍成圓排列,求不同的排列總數(shù)CP(n,r).

解要完成這個圓排列,需先從n個元素中取r個,再將其組成圓排列,故

【例1.3.3】將5個標(biāo)有不同序號的珠子穿成一環(huán),共有多少種不同的穿法?

解這是典型的項鏈排列問題.首先,由例1.3.1知,5個相異元素的圓排列共有(5-1)!=24種.其次,對于圓排列而言,將所穿的環(huán)翻過來,是另一種圓排列,但對于項鏈排列,這仍然是同一個排列(如圖1.3.1所示),故不同的排法共有24/2=12種.

一般情形,從n個相異珠子中取r個穿成一個項鏈,共有

種不同的穿法.圖1.3.1項鏈排列

1.3.5相異元素允許重復(fù)的組合

設(shè)S={∞·e1,∞·e2,…,∞·en},從S中允許重復(fù)地取r個元素構(gòu)成組合,稱為r可重組合,其組合數(shù)記為RC(∞,r).

將S的n個不同元素分別用數(shù)字1,2,…,n來表示,那么,所取出的r個元素從小到大設(shè)為a1,a2,…ar,則ai滿足:

對應(yīng)一個從n+r-1個相異元素中不允許重復(fù)地取r個元素的組合.反之,后者的一種組合也與前者的一種組合相對應(yīng).所以,兩種組合一一對應(yīng).從而

重復(fù)組合的模型是將r個無區(qū)別的球放入n個不同的盒子,每個盒子的球數(shù)不受限制.

【例1.3.4】不同的5個字母通過通信線路被傳送,每兩個相鄰字母之間至少插入3個空格,但要求空格的總數(shù)必須等于15,問共有多少種不同的傳送方式.

解5個字母的全排列數(shù)為P(5,5)=5!.對每一排列,按照位置先后的不同而有4個相異的間隔.先將12個空格均勻地放入4個間隔內(nèi),再將余下的3個(相同的)空格插入4個(不同的)間隔,其方案數(shù)即為從4個相異元素中可重復(fù)地取3個元素的組合數(shù)RC(∞,3)=C(4+3-1,3)=20.故總的傳送方式有5!·20=2400種.

1.3.6不盡相異元素的組合

設(shè)集合S={n1·e1,n2·e2,…,nt·et},n1+n2+…+nt=n,從S中任取r個,求其組合數(shù)RC(n,r).

設(shè)多項式

則RC(n,r)就是多項式中xr

的系數(shù),即

【例1.3.5】整數(shù)360有幾個正約數(shù)?

解分解360為素因子的冪的乘積

顯然,360的正約數(shù)有

即從集合S={3·2,2·3,1·5}的6個元素中任取0個、1個、……、6個的組合數(shù)之和.亦即多項式

中各項系數(shù)之和.所以

而更簡單的辦法是多項式

的系數(shù)之和實質(zhì)上就是P6(1).所以

1.4組合等式及其組合意義

組合等式的證明方法大致可歸納為以下三種:歸納法、母函數(shù)法和組合意義法.

等式1對稱關(guān)系式

組合意義從n個元素{a1,a2,…,an}中取走r個,必然余下n-r個,故從n個元素中取r個的組合與從n個元素中取n-r個的組合一一對應(yīng).

等式2加法公式

組合意義從n個元素{a1,a2,…,an}中取r個的組合,就其中某個元素,不妨設(shè)為a1來看,全體組合可分為兩類:

(1)每次取出的r個元素中都含有a1.這一類組合可視為從剩下的n-1個元素中任取r-1個,然后再加上a1

而構(gòu)成的組合,其組合數(shù)為C(n-1,r-1).

(2)不含元素a1.這類組合可視為從其余n-1個元素中任取r個的組合,其數(shù)目為C(n-1,r).

兩類情況互不重復(fù),由加法法則,式(1.4.2)成立.

等式3乘法公式

組合意義這是一個在組合算式的推導(dǎo)中經(jīng)常使用的恒等式.考慮等式

等式4

組合意義從n+r+1個元素{a1,a2,…,an+r+1}中取r個的組合情況,不外乎以下r+1種:

(1)將所有組合針對a1分為兩類:即所取r個元素中含元素a1或不含元素a1,考慮不含元素a1的情形,這相當(dāng)于從n+r個元素{a2,a3,…,an+r+1}中取r個的組合,其組合數(shù)為C(n+r,r);

(2)仿照(1),再將含有元素a1的所有組合針對a2分為兩類:即所取r個元素中含a2或不含a2,同樣考慮不含a2的情形,這又相當(dāng)于從除去a1、a2后的n+r-1個元素{a3a4,…,an+r+1}中取r-1個,再加上a1而構(gòu)成組合,其組合數(shù)為C(n+r-1,r-1)

(3)同法,r-1組合中含元素a1、a2

,但不含a3的組合數(shù)為C(n+r-2,r-2);

?

(r)組合中含元素a1、a2

、……、ar-1,但不含ar的組合數(shù)為C(n+1,1);

(r+1)組合中含元素a1、a2

、……、ar的組合數(shù)為C(n+1,0)=C(n,0).

各類情形的組合方案互不重復(fù),將其求和即得式(1.4.6).將組合等式(1.4.1)代入式(1.4.6)即得式(1.4.7).

等式5范德蒙(Vandermonde)恒等式

組合意義現(xiàn)有n個相異的紅球,m個相異的藍球,從n+m個球中取r個的組合,其結(jié)果必是下列情形之一:有i個紅球,r-i個藍球(i=0,1,…,r).對固定的i,應(yīng)有C(n,i)C(m,r-i)種選法.然后按照加法法則對i求和就得式(1.4.8).

特例當(dāng)m=r時,有

等式6和式公式

組合意義對n個元素而言,每一個元素都有“取”與“不取”兩種可能,并由此構(gòu)成所有狀態(tài).根據(jù)乘法法則,其總數(shù)為2n.它等于從n個元素中分別取0個,1個,……,n個元素的總組合數(shù).

等式7

組合意義n個元素中取r個組合,r為奇數(shù)的組合數(shù)目等于r為偶數(shù)的組合數(shù)(包括r=0).

例如,有4個元素a,b,c,d,設(shè)?為取0個元素的空組合,則所有組合情形如表1.4.1所示,其中同一列的兩個組合符合上述對應(yīng)關(guān)系,前4列為在第一行的奇數(shù)組合中去掉a而得到第二行的偶數(shù)組合,后4列則為加入a的情形

等式8

組合意義從n名先生、n名女士中選出n人,這n人中有一人擔(dān)任主席,并且必須為女士,考慮有多少種選法.

等式9設(shè)r,M都是自然數(shù),M≥r,則有

組合意義設(shè)想一個袋中有M個大小相同的球,其中有r個是白的,其余的是黑的.每次摸出一個球,不放回去,直至摸到白球為止.

這是一個必然事件(遲早會摸到白球),所以概率為1.

等式10當(dāng)n≥m時,

組合意義考慮從n人中選出m名正式代表及若干名列席代表的選法(列席代表人數(shù)不限,可以為0).

1.5多項式系數(shù)

當(dāng)n是正整數(shù)時,Newton二項式定理

式(1.5.1)的組合意義是:將n個相異的球放入兩個不同的盒子,其中要求a盒放入n1=r個,b盒放入n2=n-r個,且同盒的球不分次序,則方案數(shù)為

定理1.5.1設(shè)n與t均為正整數(shù),則有

定理1.5.2(x1+x2+…+xt)n展開式的項數(shù)等于C(n+t-1,n),而這些項的系數(shù)之和為tn.

【例1.5.5】今天是星期日,再過10100天是星期幾?

【例1.5.6】求證

證

1.6排列的生成算法

1.6.1序數(shù)法

最常用的數(shù)字的表示法是十進制表示法,考慮小于10r的正整數(shù)n,可以表示為下述的位權(quán)形式:

這種表示法可以推廣到任意的p進制數(shù),即任何小于pr的正整數(shù)都可唯一表示為

因此,滿足式(1.6.2)的序列(1.6.3)共有n!個,正好與從0到n!-1的n!個數(shù)一一對應(yīng).從而啟發(fā)我們可以在序列(1.6.3)和某一組n個元素的全排列之間建立一一對應(yīng)關(guān)系,再從序列(1.6.3)得到一種生成排列的算法.不失一般性,設(shè)n個元素為1,2,…,n.對應(yīng)規(guī)則如下:

設(shè)序列(an-1,an-2,an-3,…,a2,a1)對應(yīng)某個排列(p)=p1p2…pn,其中ai可以看作排列(p)中數(shù)i+1所在位置后面比i+1小的數(shù)的個數(shù),即排列(p)中從數(shù)i+1開始向右統(tǒng)計不大于i的數(shù)的個數(shù).

1.6.2字典序法

顧名思義,這種方法的思想就是將所有n元排列按“字典順序”排成隊,以12…n為第一個排列,排序的規(guī)則,也就是由一個排列(p)=(p1p2…pn)直接生成下一個排列的算法可歸結(jié)為:

例如,設(shè)p1p2p3p4=3421,那么,i=2,j=2,p1與p2交換得p1p2p3p4=4321,再將321逆轉(zhuǎn)即得下一個排列4123.

當(dāng)n=4時,由字典序法所得的全部排列的先后順序如下:

1.6.3鄰位互換生成算法

本算法的思想也是希望以(12…n)作為n個元素1,2,…,n的第一個排列,然后按照某種方法,由一個排列(p)=(p1p2…pn)接生成下一個排列,直到全部排列生成完畢為止.

以n=4為例,開始在排列1234的各數(shù)上方加一個左箭頭“←”,當(dāng)一個數(shù)上方箭頭所指的一側(cè),相鄰的數(shù)比該數(shù)小時,便稱該數(shù)處于活動狀態(tài).例如1←2←3←4←中的2,3,4都處于活動狀態(tài).

從排列(p)=(p1p2…pn)生成下一個排列的算法如下:

(1)若排列(p)=(p1p2…pn)中無一數(shù)處于活動狀態(tài),則停止,否則轉(zhuǎn)(2);

(2)求所有處于活動狀態(tài)的數(shù)中的最大者,設(shè)為k,k和它的箭頭所指的一側(cè)的相鄰數(shù)互換位置,轉(zhuǎn)(3);

(3)令比k大的所有數(shù)的箭頭改變方向,轉(zhuǎn)(1).n=4時各個數(shù)移動位置而生成所有4排列的情形見圖1.6.1.圖1.6.1排列的鄰位互換過程

1.7組合的生成算法

現(xiàn)以從6個元素1,2,3,4,5,6中取3個的組合為例,從中找出規(guī)律來,算法便自然形成了.

從上面的生成過程可以看出如下規(guī)律:

1.8應(yīng)用舉例

【例1.8.1】由1,2,3,4,5這五個數(shù)字能組成多少個大于43500的五位數(shù)?

解顯然,這是求有限制條件的RP(∞,5)的問題.下列情況之一發(fā)生便可導(dǎo)致“大于43500”:(1)萬位上數(shù)字是5,其余四位上的數(shù)字從1,2,3,4,5中允許重復(fù)選取,共有54個符合要求的數(shù);

(2)萬位上數(shù)字為4,千位上數(shù)字從4,5中選一個,其余三位上數(shù)字可從五個數(shù)字中重復(fù)選取,共有2×53個;

(3)萬位、千位、百位上數(shù)字分別為4、3、5,其余二位上的數(shù)字可在1~5間重復(fù)選取,共有52個.由加法法則,這樣的數(shù)總計為

【例1.8.4】把r個相異物體放入n個不同的盒子里,每個盒子允許放任意個物體,而且要考慮放入同一盒中的物體的次序,共有多少種分配方案?

解本問題既不是相異元素的不重復(fù)排列,也不是簡單的重復(fù)排列.考慮第一個物體的放法有n種,把它放入某盒子后,可看作是該盒子的隔板,將盒子分成了兩部分.這樣,第二個物體的放法有n+1種,同理,第三個物體的放法有n+2種,……,第r個物體的放法有n+r-1種.由乘法原理,符合條件的方案數(shù)為

【例1.8.5】把n元集S劃分成n-3個無序非空子集(n≥4),共有多少種分法?

解此問題是典型的分配模型中球不同而盒子相同的問題,其一般求解方法見3.4.2小節(jié).此處是盒子數(shù)為n-3的特殊情形,可用排列組合的方法求解.

設(shè)共有L種分法,可將這些劃分方法分成如下三類情形分別予以統(tǒng)計:

(1)使得有一個子集是4元集,其余子集是1元集的劃分方案數(shù)等于n元集的不重復(fù)的4組合數(shù);

【例1.8.7】有7位科學(xué)家A、B、C、D、E、F、G從事一項機密工作,他們的工作室裝有電子鎖,每位科學(xué)家都有打開電子鎖的“鑰匙”.為了安全起見,必須同時有4人在場時才能打開大門.那么,該電子鎖至少應(yīng)具備多少個特征?每位科學(xué)家的“鑰匙”至少應(yīng)有多少種特征?

解任意3個人在一起,至少缺少一種特征,故不能打開電子鎖.由7個人中任選3人的組合數(shù)為C(7,3),故電子鎖至少應(yīng)有

種特征.這樣才能保證有任意3人在場時至少缺少一個特征而打不開大門.這就是說,每一種組合所形成的3人小組缺少的特征是不一樣的,才能達到目的.如若不然,假設(shè)電子鎖只有34種特征,那么,7人中取3位的35種組合方案中,至少有兩組缺少同一種特征,而這兩種組合方案至少對應(yīng)4位不同的科學(xué)家(當(dāng)然至多6人),這就說明,這4位科學(xué)家由于缺少同一特征而當(dāng)4人同時在場時打不開大門.

對科學(xué)家A的“鑰匙”而言,其余6個人中任意3個人在場,至少缺少一個A所具有的特征而無法打開大門.所以該科學(xué)家的“鑰匙”至少要有

種特征.同樣的道理,這也就是說,對于其余6個人取3人的20種組合方案,任何兩種方案對應(yīng)的兩組科學(xué)家,兩組各缺少的特征也是不一樣的.否則,假如A的鑰匙不夠20種特征,比方說只有19種特征,那么,由于其余6人中的任意3位既不能打開大門,而且加上這個科學(xué)家又能打開大門,因而,6人的每一種3組合都缺少A的某個特征.現(xiàn)在,A只有19種特征,組合方案有20種,故必有兩種組合缺A的同一特征,而這兩種組合同樣至少含有4位科學(xué)家,那么,這4位同時在場時又打不開大門了.

這是信息共享的一種方法.給每位科學(xué)家分配“鑰匙”的思路之一就是先寫出7位科學(xué)家的所有3組合,并按序編號如下:

給第i組的每個科學(xué)家不分配第i個特征,則可得每個科學(xué)家應(yīng)掌握的“鑰匙”特征編號如下:

【例1.8.8】從(0,0)點到達(m,n)點(m<n)(見圖1.8.1(a)),要求中間所經(jīng)過的每一個格子點(a,b)恒滿足b>a,問有多少條最短路徑.

解從(0,0)到(m,n)點的路徑中若排除經(jīng)過點(a,b),b≤a的可能性,則第一步必須從(0,0)到(0,1).因此問題等價于求滿足條件的從(0,1)點到(m,n)點的路徑數(shù).圖1.8.1帶有限制條件的最短路徑問題

故所求的路徑數(shù)為(0,1)點到(m,n)點的所有路徑數(shù)減去(1,0)點到(m,n)點的所有路徑數(shù),即

1.9斯特靈(Stirling)近似公式

在組合數(shù)學(xué)中經(jīng)常遇到n!的計算,隨著n的增大,結(jié)果增長迅速.斯特靈公式給出一個求n!的近似公式,它對從事計算和理論分析都是有意義的.斯特靈公式是這樣的:

這里符號~表示它的兩端的比值,隨著n的無限增大而趨于1,也就是

即相對誤差隨著n的趨向無窮而趨于零.然而絕對誤差并非如此,實際上

1.9.1Wallis公式

在證明上述n!的近似公式時,要用到Wallis公式,即

1.9.2Stirling公式

計算定積分

將定積分區(qū)間[1,n]分為n個小區(qū)間:[1,2],[2,3],…,[n-1,n],用梯形公式計算An的近似積分.可得

另一方面,令第二章母函數(shù)及其應(yīng)用2.1母函數(shù)2.2母函數(shù)的性質(zhì)2.3指數(shù)型母函數(shù)2.4正整數(shù)的分拆

在第一章中,已經(jīng)解決了部分排列組合方案的計數(shù)問題.但對于不盡相異元素的部分排列和組合,用第一章的方法是比較麻煩的(參見表2.0.1).若改用母函數(shù)方法,問題將顯得容易多了.其次,在求解遞推關(guān)系的解、整數(shù)分拆以及證明組合恒等式時,母函數(shù)方法是一種非常重要的手段.

2.1母函數(shù)

定義2.1.1對于數(shù)列{an},稱無窮級數(shù)為該數(shù)列的普通型母函數(shù),簡稱普母函數(shù)或母函數(shù),同時稱{an}為G(x)的生成數(shù)列.

【例2.1.1】有限數(shù)列C(n,r),r=0,1,2,…,n的普母函數(shù)是(1+x)n.

【例2.1.2】無限數(shù)列{1,1,…,1,…}的普母函數(shù)是

說明

(1)an的非零值可以為有限個或無限個;

(2)數(shù)列{an}與母函數(shù)一一對應(yīng),即給定數(shù)列便得知它的母函數(shù);反之,求得母函數(shù)則數(shù)列也隨之而定;

(3)這里將母函數(shù)只看作一個形式函數(shù),目的是利用其有關(guān)運算性質(zhì)完成計數(shù)問題,故不考慮“收斂問題”,即始終認(rèn)為它是收斂的,而且是可“逐項微分”和“逐項積分”的.

表2.1.1是一些常用的母函數(shù),它們的證明只要利用解析函數(shù)展開成冪級數(shù)的方法即可得到.

定理2.1.1組合的母函數(shù):設(shè)S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,則S的r可重組合的母函數(shù)為

其中,r可重組合數(shù)為xr之系數(shù)ar,r=0,1,2,…,n.

定理2.1.1的最大優(yōu)點在于:

(1)將無重組合與重復(fù)組合統(tǒng)一起來處理;

(2)使處理可重組合的枚舉問題變得非常簡單.

推論6設(shè)S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,要求元素ei至少出現(xiàn)ki

次,則S的r可重組合的母函數(shù)為

【例2.1.3】設(shè)有2個紅球,1個黑球,1個白球,問:

(1)共有多少種不同的選取方法.試加以枚舉.

(2)若每次從中任取3個,有多少種不同的取法.

【例2.1.4】有18張戲票分給甲、乙、丙、丁4個班(不考慮座位號),其中,甲、乙兩班最少1張,甲班最多5張,乙班最多6張;丙班最少2張,最多7張;丁班最少4張,最多10張.可有多少種不同的分配方案?

【例2.1.5】從n雙互相不同的鞋中取出r只(r≤n),要求其中沒有任何兩只是成對的,共有多少種不同的取法?

這實際上是一種二次分配問題.即將r個相同的球放入n個不同的盒子,第i個盒子最多放ti個球,而該盒子又分為ni個相異的格子,每個格子最多只能放一個球,故還需要進行二次分配.如果第i個盒子中放進了ri個球,那么,對該盒子而言,二次分配時的方案數(shù)為.

例如,設(shè)甲、乙、丙3個班分別有30、28、22名學(xué)生,現(xiàn)把5本相同的書分給甲、乙、丙3個班,再發(fā)到個人手上,每人最多發(fā)一本.考慮將分給某班的某本書發(fā)給該班的同學(xué)A與將其發(fā)給同學(xué)B被認(rèn)為是不同的分法,而且甲、乙兩班最少1本,甲班最多5本,乙班最多6本,丙班最少2本,最多9本,問共有多少種不同的分配方案.

【例2.1.6】甲、乙、丙3人把n(n≥3)本相同的書搬到辦公室,要求甲和乙搬的本數(shù)一樣多,問共有多少種分配的方法.

解本問題即組合問題:從集合S={∞·e1,∞·e2,∞·e3}中可重復(fù)地選取n個元素,但要求e1與e2的個數(shù)一樣多,求不同的選取方案數(shù).

設(shè)想當(dāng)n=1時,其分法只有1種,即甲和乙都分0本,丙分1本.當(dāng)n=2時,其分法有2種:甲和乙都分0本(丙分2本)或甲和乙都分1本(丙分0本).當(dāng)n=3時,也是2種分法.

當(dāng)n=4或5時,分法為3種:即甲和乙都分0本、1本或2本

一般情形,甲分k本,乙也必須分k本,丙就只能分n-2k本.考慮將分配過程分為3步實現(xiàn).第一步先選出2k本書,第二步將選出的書分給甲、乙各一半,第三步將剩下的書全分給丙.由于第二步屬于二次分配,且只有一種分法,故可以將甲和乙視為一人,從而把問題轉(zhuǎn)換為:將n本相同的書分給兩個人,其中一人分得偶數(shù)本,求分配方法數(shù).顯然,本問題的母函數(shù)為

【例2.1.7】證明組合等式

證本例是母函數(shù)的另一種應(yīng)用.意圖說明普母函數(shù)除了能用于解決組合的求值問題之外,還能用來證明很多組合等式.

(3)因為

2.2母函數(shù)的性質(zhì)

由于母函數(shù)與它的生成數(shù)列之間是一一對應(yīng)的,因此,若兩個母函數(shù)之間存在某種關(guān)系,則對應(yīng)的生成數(shù)列之間也必然存在相應(yīng)的關(guān)系.反之亦然.利用這類對應(yīng)關(guān)系,常常能幫助我們構(gòu)造出某些指定數(shù)列的母函數(shù)的有限封閉形式.特別地,還能得到一些求和的新方法.設(shè)數(shù)列{ak}、{bk}、{ck}的母函數(shù)分別為A(x)、B(x)、C(x),且都可逐項微分和積分

2.3指數(shù)型母函數(shù)

但是,注意到n集的r無重排列數(shù)和r無重組合數(shù)之間有如下關(guān)系:

從而有

定義2.3.1對于數(shù)列{ak}={a0,a1,a2,…},把形式冪級數(shù)

稱為數(shù)列{ak}的指數(shù)型母函數(shù),簡稱為指母函數(shù),而數(shù)列{ak}則稱為指母函數(shù)Ge(x)的生成序列.

說明

(1)ak的非零值可以為有限個或無限個.

(2)數(shù)列{ak}與母函數(shù)一一對應(yīng),即給定數(shù)列便得知它的指母函數(shù);反之,求得指母函數(shù)則數(shù)列也隨之而定.

(3)這里將指母函數(shù)只看做一個形式函數(shù),目的是利用其有關(guān)運算性質(zhì)完成計數(shù)問題,故不考慮“收斂問題”,即始終認(rèn)為它是收斂的,而且是可“逐項微分”和“逐項積分”的.

(4)相應(yīng)于同一數(shù)列{ak},一般G(x)≠Ge(x).

定理2.3.1設(shè)重集S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,則S的r可重排列的指母函數(shù)為

其中,r可重排列數(shù)為xr/r!之系數(shù)ar,r=0,1,2,…,n.

【例2.3.1】盒中有3個紅球,2個黃球,3個藍球,從中取4個球,排成一列,問共有多少種不同排列方案.

所以,從中取4個球的排列方案有70種.

類似于組合問題,令

即對全部排列方案進行分類枚舉.可以看出,取1個球的3種排列方案為紅、黃、藍各分別取1個.取2個球的9種排列方案為:紅紅、黃黃、藍藍、紅黃、黃紅、紅藍、藍紅、黃藍、藍黃.其它情形依此類推.

這里需要說明的是:

(1)在例2.1.3中,利用普母函數(shù)可以將組合的每一種情況都枚舉出來,但是對排列問題,指母函數(shù)卻做不到,只能對排列進行分類枚舉.正如例2.3.1這樣,項ryb的系數(shù)6說明紅、藍、黃球各取一個時,有6種排列方案,但每一種方案具體是什么,則無法表示出來了.

推論1若S={e1,e2,…,en},則r無重排列的指母函數(shù)為

推論2若S={∞·e1,∞·e2,…,∞·en},則r無限可重排列的指母函數(shù)為

排列數(shù)為nr

推論3

S={n1·e1,n2·e2,…,nm·em},元素ei至少取ki個(ki≥0),則有

推論4S={n1·e1,n2·e2,…,nm·em

},令r=n,即得全排列數(shù)

【例2.3.2】五個數(shù)字1,1,2,2,3能組成多少個四位數(shù)?

由a4=30知能組成30個四位數(shù).同時還知道能組成3個一位數(shù),8個兩位數(shù),18個三位數(shù)等.

【例2.3.3】求1,3,5,7,9五個數(shù)字組成的n位數(shù)的個數(shù)(每個數(shù)字可重復(fù)出現(xiàn)),要求其中3,7出現(xiàn)的次數(shù)為偶數(shù),1,5,9出現(xiàn)的次數(shù)不加限制.

【例2.3.4】把上例的條件改為要求1、3、7出現(xiàn)的次數(shù)一樣多,5和9出現(xiàn)的次數(shù)不加限制.求這樣的n位數(shù)的個數(shù).

解設(shè)滿足條件的數(shù)有bn個,與例2.1.6的分配問題類似,即將n個不同的球放入標(biāo)號為1、3、5、7、9的5個盒子,其中盒子1、3、7中的球一樣多.考慮把此3個盒子視為一個大盒子,大盒子中分為3個小盒子.問題即轉(zhuǎn)化為將n個不同的球放入A、B、C這3個不同的盒子,其中盒子A里球的個數(shù)應(yīng)為3k(k≥0),且A中的球第二次被分到3個不同的小盒子中,每個盒子恰好放入k個球,有種分法.所以,本問題的指母函數(shù)為

【例2.3.5】在例2.1.5中,若把所取出的r只鞋再排成一列,問共有多少種結(jié)果.

解此問題即是從集合S={e11,e12,e21,e22,…,en1,en2}的n類共2n個元素中不重復(fù)地取出r個元素排成一列,且同一類元素ei1,ei2不能同時出現(xiàn)(1≤i≤n).因此,其r個元素?zé)o重排列的指母函數(shù)應(yīng)為

即不同的排列共有

從分配角度看問題,就是將r個不同的球放入n個不同的盒子,每個盒子最多放一個球,而且每個盒子中有兩個相異的格子,故還需要進行二次分配.如果某個盒子中放進一個球,那么,二次分配時有兩種可選的方案.

2.4正整數(shù)的分拆

定義2.4.1將一個正整數(shù)n分解成k個正整數(shù)之和稱該分解是n的一個k分拆,并稱ni

為分量.

此外,按照對諸ni

是否要考慮順序,將分拆分為兩類.例如5的兩個4分拆:

若考慮ni

間的順序,這兩個分拆被認(rèn)為是不同的,這樣的分拆稱為有序分拆.否則,不考慮順序,這時可把右端按大小重新排列且看作是同一分拆,稱為無序分拆.

2.4.1有序分拆

求n的k有序分拆的個數(shù),相當(dāng)于求一次不定方程(2.4.1)全體正整數(shù)解的組數(shù),可對每個分量ni加以條件限制,例如1≤ni≤ri(i=1,2,…,k),于是可得如下結(jié)果.

定理2.4.1對于n的k有序分拆

其k有序分拆數(shù)數(shù)列{qk(n)}的母函數(shù)是

推論若對n的k有序分拆的各分量ni

沒有限制,則其k有序分拆數(shù)數(shù)列{qk(n)}的母函數(shù)是且qk(n)=C(n-1,k-1).

2.4.2無序分拆

由前面的定義可以看出,在n的分拆中,如果不考慮各分量的順序,為討論方便起見,可把分拆后的各項數(shù)值從大到小加以排列,即有

滿足以上條件的每一組正整數(shù)解(n1,n2,…,nk)就代表了一個n的k無序分拆,簡稱分拆,其分拆數(shù)記作pk(n),n1稱為最大分項.

把n分拆為最大分項等于k,其分拆數(shù)相當(dāng)于求不定方程

的整數(shù)解的組數(shù).即整數(shù)n由1,2,…,k允許重復(fù)且k至少出現(xiàn)一次的所有(由條件式(2.4.4)限制的)組合數(shù),其母函數(shù)為

其中展開式中xn

的系數(shù)即為n的最大分項等于k的分拆個數(shù).

若最大分項小于或等于k,其分拆數(shù)相當(dāng)于解不定方程

其分拆數(shù)列的母函數(shù)為

其中展開式中xn

的系數(shù)即為n的最大分項不超過k的分拆個數(shù).

2.4.3弗雷斯(Ferrers)圖

一個從上而下的k層格子,設(shè)mi為第i層的格子數(shù),當(dāng)mi≥mi+1(i=1,2,…,n-1),即上層的格子數(shù)不少于下層的格子數(shù)時,稱之為Ferrers圖.如圖2.4.1所示.圖2.4.1共軛Ferrers圖

Ferrers圖具有以下性質(zhì):

(1)每一層至少有一個格子;

(2)Ferrers圖與式(2.4.3)說明的無序分拆是一一對應(yīng)的,其中的對應(yīng)關(guān)系是:第1層的格子數(shù)對應(yīng)分項n1,第2層的格子數(shù)對應(yīng)分項n2,……,依此類推.圖2.4.1(a)就代表20的一種分拆,即20=7+5+5+2+1.

(3)將圖形“轉(zhuǎn)置”,即把行與列對調(diào)所得的圖仍然是Ferrers圖,稱為原Ferrers圖的共軛圖(圖2.4.1中的(b)是(a)的共軛圖),或者說這兩個圖是一對共軛的Ferrers圖.若某個Ferrers圖與其共軛圖形狀相同,則稱其是自共軛的.

定理2.4.2

(1)n的所有k分拆的個數(shù)等于把n分拆成最大分項等于k的所有分拆數(shù);

(2)把n分拆成最多不超過k個數(shù)之和的分拆數(shù)等于把n分拆成最大分項不超過k的所有分拆數(shù).

推論正整數(shù)n分拆成互不相同的若干個奇數(shù)的和的分拆數(shù),等于有n個格子的自共軛的Ferrers圖的個數(shù).

證設(shè)

構(gòu)造一Ferrers圖,其第一行、第一列都是n1+1個格子,對應(yīng)于2n1+1,第二行、第二列都是n2+1個格子,對應(yīng)于2n2+1,依此類推.由此所得的Ferrers圖是自共軛的.反過來也一樣.例如

對應(yīng)的Ferrers圖如圖2.4.2所示.圖2.4.2n分拆為不同的奇數(shù)及其對應(yīng)的自共軛的Ferrers圖

2.4.4分拆數(shù)的估計

對于n的k無序分拆,當(dāng)k任意時(k=1,2,…,n),n的所有分拆的個數(shù)稱作n的分拆數(shù),記作p(n),即

定理2.4.3正整數(shù)n的全部分拆總數(shù)數(shù)列{p(n)}的母函數(shù)是

當(dāng)n較大時,計算p(n)是非常困難的,例如

下面給出p(n)的漸進公式和估值不等式.

定理2.4.4關(guān)于p(n)的計算,有

其中[x]表示將x四舍五入取整.

定理2.4.5設(shè)函數(shù)Q(n,m)表示正整數(shù)n的最大分項n1≤m的所有分拆數(shù),則有

定理2.4.5實質(zhì)上是函數(shù)Q(n,m)的遞歸定義,其原因如下:

(1)顯然有Q(1,n)=Q(m,1)=1;

(2)因為最大分量n1實際上不能大于n,故m>n時,Q(n,m)=Q(n,n);

(3)由于在n的所有分拆中,其1分拆只有一個,即n=n1,而其它的分拆都是n1≤n-1;

(4)因為對于正整數(shù)n,最大分項為m的分拆數(shù)由以下兩部分組成:一個是以m作為第一分項,其余分項之和等于n-m,且最大分項n2不超過m的分拆數(shù)Q(n-m,m);另一個是最大分項n1≤m-1的分拆數(shù)Q(n,m-1).

2.4.5應(yīng)用

【例2.4.1】設(shè)有1克、2克、3克、4克的砝碼各一枚,若要求各砝碼只能放在天平的一邊.問能稱出哪幾種重量?有哪幾種可能方案?

解這是典型的正整數(shù)分拆問題.比如說可以稱6克重的物品,使用的砝碼可以是1克、2克、3克的三個砝碼放在一起,也可以是2克和4克的兩個砝碼放在一起來稱.即當(dāng)最大分項不超過4時,6的無序不重復(fù)分拆只有兩種

首先,將整數(shù)n分拆為最大分項不超過4,且各分項最多只能出現(xiàn)一次的分拆數(shù)數(shù)列的母函數(shù)為(即在式(2.4.6)中令0≤xi≤1而得到的式(2.4.7)的特殊情形)

從右端的母函數(shù)知可稱出從1克到10克共10種重量,冪xn的系數(shù)即為稱出n克重量的方案數(shù).

若要枚舉出具體的稱重方案,則分拆數(shù)的母函數(shù)應(yīng)為

【例2.4.2】求用1分、2分、3分的郵票貼出不同面值的方案數(shù).

【例2.4.3】在例2.4.2中,按照有序分拆,貼成總面值等于4分的方案數(shù)是多少?

【例2.4.4】若有1克的砝碼3枚,2克的4枚,4克的2枚,問能稱出多少種重量.各有幾種方案?

【例2.4.5】在例2.4.4中,若砝碼可以放在天平的兩邊,但兩邊不能同時有同樣重量的砝碼,請給出問題的母函數(shù).問要稱出2g重的物體,有多少種不同的稱法?并給出每一種稱法.

若要枚舉每一種稱法,可用3個符號x、y、z分別代表不同的砝碼,構(gòu)造該問題的母函數(shù)如下:

從上邊的多項式可以看出,稱2g重物體的具體稱法為(負數(shù)表示砝碼與物體在天平的同一邊,正數(shù)表示砝碼放在另一邊):

像下邊這些稱法,用上邊的母函數(shù)是反映不出來的(即天平兩邊放有同一重量的砝碼,使得相同砝碼抵消):

【例2.4.6】投擲3個骰子,點數(shù)之和為n(3≤n≤18),其方案有多少種?骰子的情況如下:(1)3個骰子相異;(2)3個骰子相同.

(2)3個骰子相同,則問題等價于n的特殊無序3分拆.其特殊性體現(xiàn)在對每個分量的值都限制在1~6之間,即

其中點數(shù)之和等于n的方案數(shù)就是xn的系數(shù)(3≤n≤18).例如點數(shù)之和等于10的方案有6種,即

這也是10的每個分項值不超過6的無序3分拆數(shù).第三章遞推關(guān)系3.1基本概念3.2常系數(shù)線性遞推關(guān)系3.3解遞推關(guān)系的其它方法3.4三種典型數(shù)列3.5應(yīng)用

3.1基本概念

定義3.1.1a對數(shù)列{ai|i≥0}和任意自然數(shù)n,一個關(guān)系到an

和某些個ai(i<n)的方程式,稱為遞推關(guān)系,記作上式只是一種定義方式,也稱為隱式定義.另外,也有顯式定義.

定義3.1.1b對數(shù)列{ai|i≥0},把an與其前若干項聯(lián)系起來的等式對所有n≥k均成立(k為某個給定的自然數(shù)),稱該等式為{ai}的遞推關(guān)系,記為

分類除了有顯式與隱式之分外,還有如下的分法:

(1)按常量部分:①齊次遞推關(guān)系:即常量=0,

如Fn=Fn-1+Fn-2;②非齊次遞推關(guān)系,即常量≠0,如hn-2hn-1=1.

(2)按ai的運算關(guān)系:

①線性關(guān)系:F是關(guān)于ai的線性函數(shù),

如(1)中的Fn與hn均是如此;

②非線性關(guān)系:F是ai的非線性函數(shù),

如hn=h1hn-1+h2hn-2+…+hn-1h1.

(3)按ai的系數(shù)分:

①常系數(shù)遞推關(guān)系,如(1)中的Fn與hn;

②變系數(shù)遞推關(guān)系,如pn=npn-1,pn-1之前的系數(shù)是隨著n而變的.

(4)按數(shù)列的多少:①一元遞推關(guān)系:指方程只涉及一個數(shù)列,如式(3.1.1a)和(3.1.1b)均為一元的;②多元遞推關(guān)系:指方程中涉及多個數(shù)列,如

以上所給出的例子都是顯式的或者可以化為顯式關(guān)系(如(1)中的hn).而在求微分方程的數(shù)值解時,還會碰到如下的隱式遞推關(guān)系:

定義3.1.2(定解問題)稱含有初始條件的遞推關(guān)系為定解問題,其一般形式為

所謂解遞推關(guān)系,就是指根據(jù)式(3.1.1a)或(3.1.2)求an

的且與a0、a1、……、an-1無關(guān)的解析表達式或數(shù)列{an}的母函數(shù).

【例3.1.1】(Hanoi塔問題)這是組合學(xué)中著名的問題.n個圓盤按從小到大的順序依次套在柱A上,如圖3.1.1所示.規(guī)定每次只能從一根柱子上搬動一個圓盤到另一根柱子上,且要求在搬動過程中不允許大盤放在小盤上,而且只有A、B、C三根柱子可供使用.用an

表示將n個盤從柱A移到柱C上所需搬動圓盤的最少次數(shù),試建立數(shù)列{an}的遞推關(guān)系.圖3.1.1Hanoi塔問題

解易知,a1=1,a2=3,對于任何n≥3,現(xiàn)設(shè)計搬動圓盤的算法如下:第一步,將套在柱A的上部的n-1個盤按要求移到柱B上,共搬動了an-1次;第二步,將柱A上的最大一個盤移到柱C上,只要搬動一次;第三步,再從柱B將n-1個盤按要求移到柱C上,也要用an-1次.由加法法則,{an}的定解問題為

【例3.1.2】(藍開斯特(Lancaster)戰(zhàn)斗方程)兩軍打仗,每支軍隊在每天戰(zhàn)斗結(jié)束時都清點人數(shù),用a0和b0分別表示在戰(zhàn)斗打響前第一支和第二支軍隊的人數(shù),用an和bn分別表示第一支和第二支軍隊在第n天戰(zhàn)斗結(jié)束時的人數(shù)，那么,an-1-an

就表示第一支軍隊在第n天戰(zhàn)斗中損失的人數(shù)，同樣,bn-1-bn表示第二支軍隊在第n天戰(zhàn)斗中損失的人數(shù)

假設(shè)一支軍隊所減少的人數(shù)與另一支軍隊在每天戰(zhàn)斗開始前的人數(shù)成比例,因而有常數(shù)A和B,使得

其中常量A、B是度量每支軍隊的武器系數(shù),將上述等式改寫成

這是一個含有兩個未知量的一階線性遞推關(guān)系組.

【例3.1.3】設(shè)

求{an}所滿足的遞推關(guān)系.

解分兩種情況:當(dāng)n為偶數(shù)時,令n=2m,則

其中[]稱為下整函數(shù),其值定義為不大于x的最大整數(shù)。于是an

可寫成

于是得

當(dāng)n為奇數(shù)時,同樣可證上述遞推關(guān)系成立.

因此,an所滿足的遞推關(guān)系是

另外,顯然有a0=a1=1

3.2常系數(shù)線性遞推關(guān)系

常系數(shù)的線性遞推關(guān)系總可以化為如下形式:或分別稱為k階齊次遞推關(guān)系和k階非齊次遞推關(guān)系.其中f(n)稱為自由項.

3.2.1解的性質(zhì)

3.2.2解的結(jié)構(gòu)

定義3.2.1稱多項式

為齊次遞推關(guān)系式(3.2.1)的特征多項式,相應(yīng)的代數(shù)方程C(x)=0稱為式(3.2.1)的特征方程,特征方程的解稱為式(3.2.1)的特征根.

定理3.2.1數(shù)列an=qn是式(3.2.1)的非零解的充分必要條件是q為式(3.2.1)的特征根.

證

an=qn是式(3.2.1)的解?qn+c1qn-1+…+ckqn-k=0?qk+c1qk-1+…+ck=0?q是方程C(x)=0的根,即q是式(3.2.1)的特征根.

定理3.2.1的意義在于將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)化為常系數(shù)代數(shù)方程的求根問題,從而給出了一個實用且比較簡單的解此類遞推關(guān)系的方法.

定義3.2.2若{a(1)

n},{an(2)},…,{an(s)}是式(3.2.1)的不同解,且式(3.2.1)的任何解都可以表為r1an(1)+r2an(2)+…+rsan(s)=an,則稱an為式(3.2.1)的通解.其中r1,r2,…,rs為任意常數(shù).

此處所說的不同解是指將每一個解{an(i)}都視為一個無窮維的解向量,而這些向量之間是線性無關(guān)的.

所以,通解an=r1an(1)+r2an(2)+…+rsan(s)應(yīng)具備如下3個特征:

(1)通解首先是解,這由性質(zhì)1即可看出.

(2)組成通解的所有解向量線性無關(guān).

(3)任何一個具體的解都被包容在通解an中.

3.2.3特征根法

該方法的思路就是通過解式(3.2.1)的特征方程,從而求得其特征根,再利用特征根即可獲得式(3.2.1)的通解.根據(jù)特征根的不同分布情況,分為下述三種情形予以討論.

1.特征根為單根情形

設(shè)q1,q2,…,qk是式(3.2.1)的互不相同的特征根,則式(3.2.1)的通解為

其中A1,A2,…,Ak為任意常數(shù)(待定).

【例3.2.1】求遞推關(guān)系an-4an-1+an-2=-6an-3的通解.

解特征方程為x3-4x2+x+6=0,解之得特征根

所以通解為

其中,A、B、C為任意常數(shù).

2.重根情形

對于特征方程有重根的情形,不能直接套用單根時的方法.下面先通過實例,再歸納給出此種情況下的通解.

【例3.2.2】求遞推關(guān)系an-4an-1+4an-2=0的通解.

3.復(fù)根情形

【例3.2.4】求定解

3.2.4非齊次方程

對于非齊次方程,比較有規(guī)律的解法主要是針對f(n)的幾種特殊情形.

定理3.2.2設(shè)an*是式(3.2.2)的一個特解,是式(3.2.1)的通解,則式(3.2.2)的通解為

證首先由解的性質(zhì)知,an是式(3.2.2)的解.

其次,證明an

是通解.若給定一組初始條件

可以仿照齊次方程通解的證明方法,證得相應(yīng)于條件式(3.2.11)的解一定可以表示為式(3.2.10)的形式.

關(guān)于的求法已經(jīng)解決,這里的主要問題是求式(3.2.2)的特解an

*.遺憾的是尋求特解還沒有一般通用的方法.然而,當(dāng)非齊次線性遞推關(guān)系的自由項f(n)比較簡單時,采用下面的待定系數(shù)法比較方便.

1.f(n)=b(b為常數(shù))

其中m表示1是式(3.2.1)的m重特征根(0≤m≤k).當(dāng)然,若1不是特征根(即m=0),則an*=A.

2.f(n)=bn(b為常數(shù))

其中m表示b是式(3.2.1)的m重特征根(0≤m≤k).同樣,若b不是特征根(即m=0),則an*=Abn.

3.f(n)=bnPr(n)(其中Pr(n)為關(guān)于n的r次多項式,b為常數(shù))

其中Qr(n)是與Pr(n)同次的多項式,m仍然是b為特征根的重數(shù)(0≤m≤k).當(dāng)b不是特征根時(即m=0),an*=bnQr(n).

3.2.5一般遞推關(guān)系化簡

對于某些非線性或變系數(shù)的遞推關(guān)系,可以將其化為線性關(guān)系來求解.

【例3.2.12】設(shè)n≥1,an≥0.解定解問題

解這是非線性的遞推關(guān)系,令bn=an2,將問題變?yōu)?/p>

3.3解遞推關(guān)系的其它方法

3.3.1迭代法與歸納法

對于某些特殊的,尤其是一階的遞推關(guān)系,使用迭代法求解可能更快.而有些遞推關(guān)系則可以通過觀察n比較小時an的表達式的規(guī)律,總結(jié)或猜出an的一般表達式,然后再用歸納法證明之即可.

【例3.3.1】解遞推關(guān)系

3.3.2母函數(shù)方法

對于一些較復(fù)雜的遞推關(guān)系,利用母函數(shù)方法求解是很有效的.當(dāng)用它求解數(shù)列{an}的遞推關(guān)系時,一開始并不企圖直接找出an的解析表達式,而是首先作出{an}的母函數(shù)

由2.2節(jié)母函數(shù)的性質(zhì)3知

于是得到

【例3.3.9】用母函數(shù)方法求解二元遞推關(guān)系.

解設(shè)數(shù)列{an}的母函數(shù)為A(x),{bn}的母函數(shù)為B(x).在第一個方程的兩邊同乘

所以,原遞推關(guān)系的解為

3.4三種典型數(shù)列

3.4.1Fibonacci數(shù)列序列1,1,2,3,5,8,13,21,34,…中,每個數(shù)都是它前兩者之和,這個序列稱為Fibonacci數(shù)列.由于它在算法分析和近代優(yōu)化理論中起著重要作用,又具有很奇特的數(shù)學(xué)性質(zhì),因此,1963年起美國就專門出版了針對這一數(shù)列進行研究的季刊《FibonacciQuarterly》.

該數(shù)列來源于1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個有趣的兔子問題:有雌雄一對小兔,一月后長大,兩月起往后每月生(雌雄)一對小兔.小兔亦同樣如此.設(shè)一月份只有一對小兔,問一年后共有多少對兔子?

更一般地,此問題可以變?yōu)閚個月后共有多少對兔子?

將開始有第一對小兔的月份視為第一個月,用Fn表示在第n個月的兔子數(shù),顯然F1=F2=1.其次,可以看出．

【例3.4.1】(上樓梯問題)某人欲登上n級樓梯,若每次只能跨一級或兩級,他從地面上到第n級樓梯,共有多少種不同的方法?

解設(shè)上到第n級樓梯的方法數(shù)為an.那么,第一步無非有兩種可能:

(1)跨一級,則余下的n-1級有an-1種上法;

(2)跨兩級,則余下的n-2級有an-2種上法

【例3.4.2】棋盤染色問題:給一個具有1行n列的1×n棋盤(見圖3.4.1)的每一個方塊涂以紅、藍二色之一,要求相鄰的兩塊不能都染成紅色,設(shè)不同的染法共有an

種,試求an.圖3.4.11×n棋盤

【例3.4.3】交替子集問題:有限整數(shù)集合Sn={1,2,…,n}的一個子集稱為交替的,如果按上升次序列出其元素時,排列方式為奇、偶、奇、偶、…….例如{1,4,7,8}和{3,4,11}都是,而{2,3,4,5}則不是.令gn表示交替子集的數(shù)目(其中包括空集),證明

且有g(shù)n=Fn+2.

證顯然,g1=2,對應(yīng)S1的交替子集為?和{1}.g2=3,對應(yīng)S2的交替子集為?、{1}、{1,2}.

將Sn

的所有子集分為兩部分:

(1)Sn-1={1,2,…,n-1}的所有子集;

(2)Sn-1的每一個子集加入元素n后所得子集.

例如,n=4,S4={1,2,3,4}的所有子集劃分為兩類,即

(1)?、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3};

(2){4}、{1,4}、{2,4}、{3,4}、{1,2,4}、{1,3,4}、{2,3,4}、{1,2,3,4}.

【例3.4.4】(棋盤的(完全)覆蓋問題)本例的棋盤覆蓋是指用規(guī)格為1×2的骨牌覆蓋p×q的方格棋盤,要求每塊骨牌恰好蓋住盤上的相鄰兩格.所謂完全覆蓋,是指對棋盤的一種滿覆蓋(即盤上所有格子都被覆蓋),而且骨牌不互相重疊.容易看出,一定存在對2×n棋盤的完全覆蓋.現(xiàn)在的問題是,究竟有多少種不同的完全覆蓋方案?

解設(shè)所求方案數(shù)為gn.那么,對圖3.4.2最左面的四格有且僅有兩種可能的覆蓋方式:

(1)一塊骨牌豎著放,覆蓋最左面的兩格11和21,則整個棋盤的這種完全覆蓋方式與2×(n-1)棋盤的完全覆蓋一一對應(yīng),共有g(shù)n-1種方案;

(2)一塊骨牌橫著放,覆蓋第一行的格子11和12,由于是完全覆蓋,因此第二行最左面的兩格21和22也一定被同一塊骨牌覆蓋.于是整個棋盤的這種完全覆蓋方式與2×(n-2)棋盤的完全覆蓋數(shù)相等,有g(shù)n-2種方案.

由加法原理,本例的定解問題為

所以圖3.4.22×n棋盤

3.4.2Stirling數(shù)列

下階乘函數(shù)

在組合分析和有限差分學(xué)中的地位,如同冪函數(shù)xn在數(shù)學(xué)分析中的地位,具有重要的作用,又都是首項系數(shù)為1的特殊的n次多項式,而且可以互相表示.

如:

定義3.4.1設(shè)

則稱S1(n,k)、S2(n,k)分別為第一類和第二類Stirling數(shù).

Striling數(shù)的組合意義:

(1)分配問題:將n個有區(qū)別的球放入m個相同的盒子,要求各盒不空,則不同的放法總數(shù)為S2(n,m);

(2)集合的劃分:將含有n個元素的集合恰好分成m個無序非空子集的所有不同劃分的數(shù)目即S2(n,m).這種劃分也稱為集合的m劃分.

定理3.4.1第一類Stirling數(shù)有如下性質(zhì):

(6)S1(n,k)滿足遞推關(guān)系

定理3.4.2第二類Stirling數(shù)有如下性質(zhì)

證(1)~(3)由組合意義可以看出,將n個球(n>0)放入0個或1個盒子的方案數(shù)分別為0或1,放入n個盒子也只有一種方案,原因在于盒子不空且不加區(qū)別.所以,性質(zhì)(1)~(3)成立.

(4)n個球放入n-1個盒,各盒不空,必有一盒有兩個球.從n個相異的球中選取2個,共有C(n,2)種組合方案.

(5)n個球,2個盒.任取某一球x,其余的n-1個球每個都有兩種可能的放法,即與x同盒或不同盒,故有2n-1種可能.但要排除大家都與x同盒的情形(這時另一盒將空),所以總的放法有2n-1-1種.

(6)從n個球中任選一個記為x,根據(jù)n的情況將x個球放入k個盒的方案分為兩類:①x獨占一盒,其余n-1個球放入另外k-1個盒,由組合意義知此類放法共有S2(n-1,k-1)種;②x不獨占一盒,相當(dāng)于先將其余n-1個球放入k個盒子,且各盒不空,有S2(n-1,k)種放法,然后再將x放入其中某盒,有k種放法.由乘法原理,此類放法共有k·S2(n-1,k)種.

根據(jù)加法法則,即知性質(zhì)(6)成立.利用上述性質(zhì),可得第二類Stirling數(shù)值表(見表3.4.2).

下面不加證明地給出Stirling數(shù)的其它結(jié)論:

【例3.4.6】Stirling數(shù)的另一個重要應(yīng)用就是分配問題:即將n個球(物體)放入k個盒子,其放法的總數(shù)可以分成8種情況分別予以討論(見表3.4.3).

說明當(dāng)然,上述8種情形還不能包括所有的分配模型,如情形1是指放入同一盒中的球是無次序之分的.否則