《組合數(shù)學(xué)》講稿2015

2023/2/4組合數(shù)學(xué)1組合

數(shù)

學(xué)主講教師鄧毅雄2023/2/4組合數(shù)學(xué)2什么是數(shù)學(xué)？數(shù)學(xué)是研究現(xiàn)實(shí)中數(shù)量關(guān)系和空間形式的科學(xué).

---恩格斯

數(shù)學(xué)是科學(xué)之母。數(shù)學(xué)教育的意義？作為工具的數(shù)學(xué)，作為素質(zhì)訓(xùn)練的數(shù)學(xué)數(shù)學(xué)是思維的體操數(shù)學(xué)知識(shí)可以記憶一時(shí),但數(shù)學(xué)的精神、思想和方法卻隨時(shí)隨地發(fā)揮作用，可以受益無窮.

2023/2/4組合數(shù)學(xué)3數(shù)學(xué)是美的嗎？哪里有數(shù),哪里就有美.

---恩格斯（學(xué)會(huì)欣賞數(shù)學(xué)？）數(shù)學(xué)的應(yīng)用？任何一門科學(xué),只有當(dāng)它充分地應(yīng)用了數(shù)學(xué)時(shí)才算很好地發(fā)展了.

---馬克思

2023/2/4組合數(shù)學(xué)4

在計(jì)算機(jī)出現(xiàn)以來，數(shù)學(xué)科學(xué)與計(jì)算機(jī)科學(xué)就始終密不可分。國內(nèi)外許多著名計(jì)算機(jī)專家是數(shù)學(xué)出身。

一方面，數(shù)學(xué)在計(jì)算機(jī)科學(xué)發(fā)展中起不可替代的作用。計(jì)算機(jī)科學(xué)的數(shù)學(xué)理論體系是相當(dāng)龐雜的，主要有數(shù)值計(jì)算，離散數(shù)學(xué)，數(shù)論，計(jì)算理論等。2023/2/4組合數(shù)學(xué)5

另一方面，使用計(jì)算機(jī)解決數(shù)學(xué)問題（和解決其他問題一樣）可能發(fā)展出一些新方法。例如先提出假說，用計(jì)算機(jī)做先期檢驗(yàn)，可能是各種簡(jiǎn)化情況的檢驗(yàn)，以考驗(yàn)假說的可能性。然后再考慮如何從理論上嚴(yán)格處理。計(jì)算機(jī)的圖形處理能力、數(shù)值計(jì)算能力和符號(hào)計(jì)算能力都可能在處理數(shù)學(xué)問題的過程中發(fā)揮作用。吳文俊院士的數(shù)學(xué)機(jī)械化研究。

2023/2/4組合數(shù)學(xué)6中國軟件發(fā)展與組合數(shù)學(xué)

在美國有一種說法，將來一個(gè)國家的經(jīng)濟(jì)實(shí)力可以直接從軟件產(chǎn)業(yè)反映出來。

縱觀全世界軟件產(chǎn)業(yè)的情況，美國處于絕對(duì)的壟斷地位。造成這種現(xiàn)象的一個(gè)根本的原因就是計(jì)算機(jī)科學(xué)在美國的飛速發(fā)展。當(dāng)今計(jì)算機(jī)科學(xué)界的最權(quán)威人士很多都是研究組合數(shù)學(xué)出身的。美國的軟件之所以能領(lǐng)先，其關(guān)鍵就在于在數(shù)學(xué)基礎(chǔ)上他們有很強(qiáng)的實(shí)力，有很多杰出的人才。美國最重要的計(jì)算機(jī)科學(xué)系（MIT，Princeton，Stanford，Harvard，Yale，….）都有一流的組合數(shù)學(xué)家。2023/2/4組合數(shù)學(xué)7

我國在軟件上的落后，要說出根本的原因可能并不是很簡(jiǎn)單的事，除了技術(shù)和科學(xué)上的原因外，可能還跟我們的文化，管理水平，教育水平，思想素質(zhì)等諸多因素有關(guān)。除去這些人文因素以外，一個(gè)最根本的原因就是我國的信息技術(shù)的數(shù)學(xué)基礎(chǔ)十分薄弱，這個(gè)問題不解決，我們就難成為軟件強(qiáng)國。組合數(shù)學(xué)是研究離散對(duì)象的數(shù)學(xué)分支，它是隨著計(jì)算機(jī)出現(xiàn)及其普遍應(yīng)用才迅速發(fā)展起來的，組合數(shù)學(xué)的發(fā)展奠定了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。2023/2/4組合數(shù)學(xué)8

高層次的軟件產(chǎn)品處處用到組合數(shù)學(xué)，更確切地說就是組合算法。計(jì)算機(jī)算法可以分為三大類，（一）組合算法，（二）數(shù)值算法（包括計(jì)算數(shù)學(xué)和與處理各種信息數(shù)據(jù)有關(guān)的信息學(xué)），（三）符號(hào)計(jì)算算法。（前兩者是傳統(tǒng)的，后者是最近發(fā)展的）吳文俊院士開創(chuàng)的機(jī)器證明方法就屬于符號(hào)計(jì)算，引起了國際上的高度評(píng)價(jià)，被稱為吳方法。符號(hào)算法和吳方法跟代數(shù)組合學(xué)也有十分密切的聯(lián)系。由于數(shù)學(xué)機(jī)械化近年來的發(fā)展和在計(jì)算機(jī)科學(xué)中的重要性，把數(shù)學(xué)機(jī)械化，科學(xué)計(jì)算和組合數(shù)學(xué)組合起來，就可以說是中國信息產(chǎn)業(yè)的基礎(chǔ)2023/2/4組合數(shù)學(xué)9

今后的計(jì)算機(jī)要向更加智能化的方向發(fā)展，其出路仍然是數(shù)學(xué)的算法和數(shù)學(xué)的機(jī)械化。

美國著名數(shù)學(xué)家、科學(xué)院院士、世界著名組合大師Gian-CarloRota教授指出：組合數(shù)學(xué)是計(jì)算機(jī)軟件產(chǎn)業(yè)的基礎(chǔ)，中國最終一定能成為一個(gè)軟件大國，但是要實(shí)現(xiàn)這個(gè)目標(biāo)的一個(gè)突破點(diǎn)就是發(fā)展組合數(shù)學(xué)。（陳永川）

胡錦濤同志在1998年接見"五四"青年獎(jiǎng)?wù)聲r(shí)發(fā)表的講話中指出，組合數(shù)學(xué)不同于傳統(tǒng)的純數(shù)學(xué)的一個(gè)分支，它還是一門應(yīng)用學(xué)科，一門交叉學(xué)科。他希望中國的組合數(shù)學(xué)研究能夠?yàn)閲业慕?jīng)濟(jì)建設(shè)服務(wù)。

2023/2/4組合數(shù)學(xué)10吳軍博士《數(shù)學(xué)之美》

自然語言處理搜索2023/2/4組合數(shù)學(xué)11

組合數(shù)學(xué)(Combinatorialmathematics)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方…...2023/2/4組合數(shù)學(xué)12

幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。5193724862023/2/4組合數(shù)學(xué)13

組合數(shù)學(xué)主要研究滿足一定條件的組態(tài)（一種安排）的存在性、計(jì)數(shù)及構(gòu)造等方面的問題。組合數(shù)學(xué)大體上可分為組合計(jì)數(shù)、組合設(shè)計(jì)、組合矩陣、組合優(yōu)化等方面。組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。但是，由于組合數(shù)學(xué)的方法往往具有一定的技巧性，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。2023/2/4組合數(shù)學(xué)14參考教材：盧開澄《組合數(shù)學(xué)》2023/2/4組合數(shù)學(xué)15第一部分

排列和組合2023/2/4組合數(shù)學(xué)16一、計(jì)數(shù)原則

(一)相等原則[例]100名選手參加網(wǎng)球單打賽，需要打多少場(chǎng)比賽才能產(chǎn)生冠軍？相等原則：設(shè)A，B是兩個(gè)有限集，如果存在由A到B上的一個(gè)一一對(duì)應(yīng)映射，則|A|＝|B|。（這里|A|表示有限集A所含元素的個(gè)數(shù)，以后也類同）相等原則主要用于：將較復(fù)雜的計(jì)數(shù)問題轉(zhuǎn)化為較簡(jiǎn)單的計(jì)數(shù)問題。2023/2/4組合數(shù)學(xué)17(二)加法原則[加法法則

] 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。集合論語言： 若|A|=m,|B|=n,A∩B=,則

|A∪B|=m+n。2023/2/4組合數(shù)學(xué)18[例]

某班選修企業(yè)管理的有18人，不選的有10人，則該班共有

18+10=28人。[例]

北京每天直達(dá)上海的客車有5次，客機(jī)有3次，則每天由北京直達(dá)上海的旅行方式有

5+3=8種。2023/2/4組合數(shù)學(xué)19[例]

設(shè)n為大于1的正整數(shù)，求滿足x+y≤n的有序正整數(shù)對(duì)（x,y）的個(gè)數(shù)。因此，由加法原則：所求有序?qū)€(gè)數(shù)為：

N＝（n-1)+(n-2)+…+1

＝n(n-1)/2。解：當(dāng)x＝1時(shí)，所有可能的有序?qū)τ衝－1個(gè)；當(dāng)x＝2時(shí)，所有可能的有序?qū)τ衝－2個(gè)，…當(dāng)x＝n－1時(shí)，所有可能的有序?qū)τ?個(gè)。2023/2/4組合數(shù)學(xué)20[乘法法則

] 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有m·n種產(chǎn)生方式。集合論語言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},

則|AB|=m·n。(三)乘法原則2023/2/4組合數(shù)學(xué)21[例]

某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自{a，b，c，d，e}，第二個(gè)字符可選自{1，2，3}，則這種字符串共有

53=15個(gè)。[例]從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有

32=6條道路。2023/2/4組合數(shù)學(xué)22[例]由數(shù)字1,2,3,4,5，（1）可以構(gòu)成多少個(gè)數(shù)字不同的四位數(shù)？（2）可以構(gòu)成多少個(gè)四位偶數(shù)？（3）可以構(gòu)成多少個(gè)數(shù)字不同的四位偶數(shù)？解：（1）其個(gè)數(shù)為：5×4×3×2＝120；（2）其個(gè)數(shù)為：5×5×5×2＝250；（3）其個(gè)數(shù)為：4×3×2×2＝48。2023/2/4組合數(shù)學(xué)23[例]

某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有

42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是44=16，而只有43=12種。在乘法法則中要注意事件A和事件B的相互獨(dú)立性。2023/2/4組合數(shù)學(xué)24[例]求n元集合A＝｛a1,a2,…,an｝的子集的個(gè)數(shù)。解：經(jīng)過n步來構(gòu)造，每步對(duì)應(yīng)元素兩種選擇：選取或不選取。也就是說，這n步中，每步均有兩種方法，所以總共有2n種方法，即n元集合A的子集的個(gè)數(shù)為2n。推廣：設(shè)有集合A＝｛k1·a1,k2·a2,…,kn·an｝，其中ki·ai

（i=1,2,…,n）表示A中有ki個(gè)ai。求集合A的子集的個(gè)數(shù)。2023/2/4組合數(shù)學(xué)25設(shè)n為正整數(shù)，p1，p2,…pk是互不相同的素?cái)?shù)，若則整除n的正整數(shù)的個(gè)數(shù)為：如300＝22·3·52，則整除300的正整數(shù)的個(gè)數(shù)為：2023/2/4組合數(shù)學(xué)26(一)n元集的r－排列定義：從n個(gè)不同的元素構(gòu)成的集合中，任取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無重排列。排列的個(gè)數(shù)用P(n,r)或Prn表示。一個(gè)排列也可看作一個(gè)字符串，r也稱為排列或字符串的長(zhǎng)度。

一般不說可重即無重。二、排列2023/2/4組合數(shù)學(xué)27

從n個(gè)中取r個(gè)的排列的典型例子（模型）是從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè)。第1個(gè)盒子有n種選擇，第2個(gè)有n-1種選擇，······，第r個(gè)有n-r+1種選擇。故有

P(n,r)=n(n-1)······(n-r+1)當(dāng)r=n時(shí)稱為全排列,記為n!。0?。?2023/2/4組合數(shù)學(xué)28

上述（無重）排列的計(jì)數(shù)相當(dāng)于將r個(gè)不同的球（將r個(gè)球編為1號(hào)到r號(hào)）放入n個(gè)不同的盒子，每盒最多一個(gè)球的方案數(shù)。公式：2023/2/4組合數(shù)學(xué)29[例]

用五種顏色給三個(gè)點(diǎn)著不同的色，問有多少種不同的著色方案？解：著色方案數(shù)為：P(5,3)＝5×4×3＝60種。[例]乒乓球隊(duì)的10名隊(duì)員中有3名主力隊(duì)員，派5名參加比賽。3名主力隊(duì)員要安排在第一、三、五位置，其余7名隊(duì)員選2名安排在第二、四位置，那么不同的出場(chǎng)安排共有多少種？解：安排的種數(shù)為：

3！P（7，2）＝252。2023/2/4組合數(shù)學(xué)30[例]由5種顏色的星狀物，20種不同花排成如下的圖案：兩邊是星狀物，中間是3朵花。問有多少種這樣的圖案？解：設(shè)所求為N。5種顏色的星狀物取兩種排列的排列數(shù)為：

P(5,2)=5×4=20；20種不同花，取3種排列的排列數(shù)為：

P(20,3)=20×19×18=6840。由乘法原則，N=20×6840=136800。2023/2/4組合數(shù)學(xué)31[例]求20000到70000間的偶數(shù)中由不同數(shù)字組成的5位數(shù)的個(gè)數(shù)。解：設(shè)所求為N。若所求的數(shù)為abcde這5位數(shù)，其中2≤a≤6，e∈{0,2,4,6,8}。①若a∈{2,4,6}，則e有4種選擇，bcd有P(10-2,3)=P(8,3)種選擇，由乘法原則，有

3×4×P(8,3)=4032種可能；②若a∈{3,5}，則e有5種選擇，bcd有P(10-2,3)=P(8,3)種選擇，由乘法原則，有2×5×P(8,3)=3360種可能。由加法原則，N=4032＋3360＝7392。2023/2/4組合數(shù)學(xué)32〔例〕求由n個(gè)相異元素a1，a2，…，an構(gòu)成的a1與a2不相鄰的全排列的個(gè)數(shù)。解：n個(gè)元素的全排列種數(shù)為n！，其中a1與a2相鄰的全排列的個(gè)數(shù)為2(n-1)!，所以，滿足題意的全排列個(gè)數(shù)為：

n!-2(n-1)!=(n-2)(n-1)!。2023/2/4組合數(shù)學(xué)33(二)n元集的r－可重復(fù)排列定義：設(shè)A是n元集，如果序列a1a2…ar的元素都屬于A，則稱該序列是n元集A的一個(gè)r－可重復(fù)排列。如設(shè)A＝{1,2,3,a,b},則123aabb是A的一個(gè)7－可重復(fù)排列；aa13b222bb是A的一個(gè)10－可重復(fù)排列。問題：這種可重復(fù)排列的個(gè)數(shù)有多少呢？2023/2/4組合數(shù)學(xué)34定理：

n元集的r－可重復(fù)排列的個(gè)數(shù)為nr。證明：（略）[例]

由1,2,3,4,5,6可組成多少個(gè)大于35000的5位數(shù)？解：分兩種情況考慮：①萬位數(shù)字為3的5位數(shù)：此時(shí)千位必為5或6，有

2×63＝432個(gè)；②萬位數(shù)字大于3的5位數(shù)：此時(shí)萬位是4，5，或6，有

3×64＝3888個(gè)。由加法原則：共有432＋3888＝4320個(gè)。2023/2/4組合數(shù)學(xué)35(三)多重集的排列定義（多重集）：由n1個(gè)a1，n2個(gè)a2，…，nk個(gè)ak，組成的集合M，記為

M＝{n1·a1，n2·a2，…，nk·ak}，稱為多重集。如果n＝n1＋n2＋…，＋nk，也稱M為n－多重集。如：M＝{4·a1，3·a2，2·a3}M＝{3·1，4·2，2·3,2·4}2023/2/4組合數(shù)學(xué)36定義（多重集的排列）：設(shè)

M＝{n1·a1，n2·a2，…，nk·ak}，π是集合A＝{a1，a2，…，ak}的一個(gè)n－可重復(fù)排列且π中有n1個(gè)a1，n2個(gè)a2，…，nk個(gè)ak，則稱π為多重集M的一個(gè)全排列，也稱π為由n1個(gè)a1，n2個(gè)a2，…，nk個(gè)ak構(gòu)成的全排列。如：M＝{3·a1，2·a2，3·a3}，π1＝a1a1a2a2a3a3a1a3是M的一個(gè)8－可重復(fù)排列；

M＝{3·1，4·2，2·3,2·4}，π2＝24113423221是M的一個(gè)11－可重復(fù)排列。

問題：這種可重復(fù)排列的個(gè)數(shù)？2023/2/4組合數(shù)學(xué)37定理：多重集M＝{n1·a1，n2·a2，…，nk·ak}的全排列的個(gè)數(shù)為：證明：設(shè)M的全排列的個(gè)數(shù)為x。以M’表示把M中的所有相同元素?fù)Q成互不相同的元素，即M’是由n1＋n2＋…＋nk個(gè)互不相同元素組成的集合。M’中元素的全排列的個(gè)數(shù)為(n1＋n2＋…＋nk)！，M’全排列也可以這樣得到：先作M的全排列，其排列數(shù)為x；再將M中全排列的相同元素?fù)Q成互不相同的元素，如n1個(gè)a1換成不同元素的排列數(shù)為n1！，其余類似。由乘法原則，這樣構(gòu)造的M’的全排列數(shù)為x·n1！n2!...nk！。由相等原則：(n1＋n2＋…＋nk)！＝x·n1！n2!...nk！，因此2023/2/4組合數(shù)學(xué)38例如：

M＝{3·a1，2·a2，3·a3}的全排列個(gè)數(shù)為

M＝{3·1，4·2，2·3,3·4}的全排列個(gè)數(shù)為：2023/2/4組合數(shù)學(xué)39(四)圓周排列問題：從n個(gè)對(duì)象中取r個(gè)沿一圓周排列，求不同的排列種數(shù)。記號(hào)計(jì)算公式：2023/2/4組合數(shù)學(xué)40[例]5對(duì)夫妻出席一宴會(huì)，圍一圓桌坐下，試問有多少種不同的坐法？若要求每對(duì)夫妻相鄰又有多少種坐法？

Q(10,10)=9!=362880;Q(5,5)·25=4！·25=768。2023/2/4組合數(shù)學(xué)41三、格路模型1.定義(棋盤)：由p×q個(gè)單位正方形拼成的長(zhǎng)為p，寬為q的長(zhǎng)方形叫做一個(gè)p×q棋盤。一個(gè)10×5的棋盤OP從O到P的一條路徑2023/2/4組合數(shù)學(xué)422.簡(jiǎn)單格路問題：從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少條路徑？y(m,n)...0...x2023/2/4組合數(shù)學(xué)43無論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個(gè)x表示x方向上的一步，一個(gè)字母y表示y方向上的一步。則(0,0)→(m,n)的每一條路徑可表示為m個(gè)x與n個(gè)y的一個(gè)多重排列。即為多重集

M={m·x,n·y}的全排列，根據(jù)前面的結(jié)論，其全排列數(shù)為相等原則2023/2/4組合數(shù)學(xué)44定理(格路計(jì)數(shù))：沿p×q棋盤上的線段，由點(diǎn)O(0,0)到點(diǎn)M(m,n)的格路的數(shù)目為：如從(0,0)到(3,7)的格路數(shù)目為：2023/2/4組合數(shù)學(xué)45推廣：設(shè)c≥a,d≥b,則由A(a,b)到B(c,d)的格路數(shù)為

B(c,d)A(a,b)如：從點(diǎn)(2,4)到點(diǎn)(7,6)的格路數(shù)為：2023/2/4組合數(shù)學(xué)46(一)n元集的r－組合定義(r－組合)：集合A的含r個(gè)元素的子集稱為A的一個(gè)r－組合。組合的全體組成的集合用C(n,r)表示，所有可能的r－組合的個(gè)數(shù)也用C(n,r)或表示。

組合的計(jì)數(shù)相當(dāng)于將r個(gè)不相同的球放入n個(gè)相同的盒子里，每盒最多一個(gè)球的方案數(shù)。

四、組合2023/2/4組合數(shù)學(xué)47

若球不同，盒子相同，則是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。故有

C(n,r)·r!=P(n,r),

C(n,r)=P(n,r)/r!=(

)=即：nrn!———r!(n-r)!從(0,0)到(m,n)格路數(shù)：2023/2/4組合數(shù)學(xué)48[例]有5本不同的法文書，7本不同的英文書，10本不同的中文書。

1)取2本不同文字的書；

2)取2本相同文字的書；

3)任取兩本書。解：1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=C(5+7+10,2)2023/2/4組合數(shù)學(xué)49[例]甲和乙兩單位共11個(gè)成員，其中甲單位7人，乙單位4人，擬從中組成一個(gè)5人小組：（1）若要求必須包含乙單位2人；（2）若要求至少包含乙單位2人；（3）若要求乙單位某一人與甲單位特定一人不能同時(shí)在這個(gè)小組。試分別求各有多少種方法。解：（1）（2）2023/2/4組合數(shù)學(xué)50（3）不妨設(shè)甲單位A與乙單位B不能同時(shí)在小組。首先A與B同時(shí)在小組的情形有所以所求為：2023/2/4組合數(shù)學(xué)51[例]

從[1,300]中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？解將[1,300]分成3類：

A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡0(mod3)}={3,6,9,…,300}.

要滿足條件，有四種解法：

1)3個(gè)數(shù)同屬于A;

2)3個(gè)數(shù)同屬于B；

3)3個(gè)數(shù)同屬于C;

4)A,B,C各取一數(shù).故共有3C(100,3)+1003=485100+10000002/4組合數(shù)學(xué)52【例】10個(gè)節(jié)目中有6個(gè)演唱、4個(gè)語言類。今編寫節(jié)目單，要求任意兩個(gè)語言類之間至少有1個(gè)演唱，問可編寫出多少種不同的演出節(jié)目單?解：設(shè)可編寫出N種不同的演出節(jié)目單．可依如下三個(gè)步驟去編寫節(jié)目單：①作6個(gè)演唱節(jié)目的全排列．有6！=720種方法；②從作成的排列的左邊、右邊及6個(gè)元形成的5個(gè)空隙這7個(gè)位置甲選出4個(gè)位置中選出4個(gè)位置，有C(7,4)=35種方法；③把4個(gè)語言類節(jié)目放在巳選出的4個(gè)位置上，每個(gè)位置放一個(gè)語言類節(jié)目，有4！=24種方法.

由乘法原則得

N=720×35×24=604800。2023/2/4組合數(shù)學(xué)53【例】今安排7人人住某旅館的5個(gè)房間．每個(gè)房間至少安排1入，有多少種不同的安排住宿的方法?由加法原則得N=4200+12600=16800種。②有兩個(gè)房間均安排2人入住的住宿方法．屬于此類住宿方法：種，解：設(shè)有N種不同的安排住宿方法，這些方法可分成如下兩類：①有1個(gè)房間安排3人入任的住宿方法：

種，2023/2/4組合數(shù)學(xué)54(二)n元集的r－可重復(fù)組合定義(r－可重復(fù)組合)：從集合A中可重復(fù)地選取r個(gè)元作成的多重集，稱為集合A的一個(gè)r－可重復(fù)組合。

設(shè)A＝{a1,a2,…,an}為n元集，則A的任一個(gè)r－可重復(fù)組合可表成{x1·a1,x2·a2,…,xn·an}，其中xi為非負(fù)整數(shù)，且x1+x2+…+xn=r。如A={a,b,c,d,e}，｛a,a,b,c,c,c,d,e,e｝={2·a,1·b,3·c,1·d,2·e}是A的一個(gè)9-可重復(fù)組合。

問題：A的r－可重復(fù)組合的個(gè)數(shù)？2023/2/4組合數(shù)學(xué)55A={1,2,3,4}，｛2·1,3·2,2·3,1·4｝

1≤1≤2≤2≤2≤3≤3≤4，

1<1+1<2+2<2+3<2+4<3+5<3+6<4+7即1<2<4<5<6<8<9<11所以｛2·1,3·2,2·3,1·4｝←→｛1,2,3,5,6,8,9,11｝。從A={a,b,c}中，可重復(fù)取6個(gè)的組合數(shù)為：2023/2/4組合數(shù)學(xué)56A={1,2,3,4,5}，取10-可重復(fù)組合：

{1，1，1，2，3，3，3，4，4，5}考慮:構(gòu)造與此可重復(fù)組合對(duì)應(yīng)的一個(gè)不可重復(fù)組合

{1，1，1，2，3，3，3，4，4，5}{1，1+1，1+2，2+3，3+4，3+5，3+6，4+7，4+8，5+9}{1，2，3，5，7，8，9，11，12，14}這個(gè)10-可重復(fù)組合相當(dāng)于從

A’={1,2,3,4,5,6,7,8,9,10,11,12,13,14}中取10個(gè)的不重復(fù)組合。2023/2/4組合數(shù)學(xué)57定理(r－可重復(fù)組合計(jì)數(shù))：n元集的r－可重復(fù)組合的個(gè)數(shù)為：定理的證明：只要證明允許重復(fù)的組合與從n+r-1個(gè)不同的元素中取r個(gè)作不重復(fù)的組合是一一對(duì)應(yīng)的。設(shè)從n個(gè)不同元素中取r個(gè)作允許重復(fù)的組合：

a1,a2,

…,ar,且a1≤a2≤…≤ar≤n(a1,a2,…,ar)(a1,a2+1,…,ak+k-1,…,ar+r-1)(a1,a2+1,…,ak+k-1,…,ar+r-1)滿足

a1<a2+1<…<ak+k-1<…<ar+r-1≤n+r-1,故是從1到n+r-1中取r作不允許重復(fù)的組合。2023/2/4組合數(shù)學(xué)58(三)組合的基本性質(zhì)1.C(n,r)=C(n,n-r)

從[1,n]去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。故C(n,r)=C(n,n-r)2023/2/4組合數(shù)學(xué)592.C(n,k)=C(n-1,k)+C(n-1,k-1)即從[1,n]取a1,a2,…,ak.設(shè)1≤a1＜a2＜…＜ak≤n,對(duì)取法分類：

a1=1,有C(n-1,k-1)種方案

a1>1,有C(n-1,k)種方案共有C(n-1,k)+C(n-1,k-1)種方案，故

C(n,k)=C(n-1,k)+C(n-1,k-1)2023/2/4組合數(shù)學(xué)60y(m,n)...0...x(m,n-1)

(m-1,n)上面等式的另外一種形式：

C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)可以用格路模型證明：{(0,0)→(m,n)}={(0,0)→(m,n-1)}∪{(0,0)→(m-1,n)}2023/2/4組合數(shù)學(xué)61由組合的計(jì)算公式：2023/2/4組合數(shù)學(xué)623.()+()+()+…+()=()[證明一]從[1,n+r+1]取a1a2…anan+1，設(shè)

a1＜a2＜…＜an＜an+1， 可按a1的取值分類：a1=1,2,3,…r,r+1.a1=1,a2…an+1取自[2,n+r+1]有()種取法nn+1n+2n+rn+r+1nnnnn+1n+rna1=2,a2…an+1取自[3,n+r+1]有()種取法n+r-1n………a1=r,a2…an+1取自[r+1,n+r+1]有()種取法n+1na1=r+1,a2…an+1取自[r+2,n+r+1]有()種取法nn2023/2/4組合數(shù)學(xué)63[證明二]格路模型：從(0,0)到(n+1,r),過且僅過一條帶箭頭的邊,而過這些邊的路徑有(從下到上)(),(),…,()故有.(

)+()+()+…+()=()nn+1n+rnnnnn+1n+2n+rn+r+1nnnnn+1r(n+1,r)

...(0,0)nn+12023/2/4組合數(shù)學(xué)644.()()=()()①選政治局,再選常委,n個(gè)中央委員選出m名政治局委員,再從其中選出k名常委②選常委,再選非常委政治局委員兩種選法都無遺漏,無重復(fù)地給出可能的方案，應(yīng)該相等。nmnn-kmkkm-k2023/2/4組合數(shù)學(xué)655.

()+()+…+()=2,

證1(x+y)

=∑(

)x

y,令x=y=1,得.組合證1[1,m]的每個(gè)元素取與不取，這樣有2m

個(gè)方案.另外，這樣的組合中，可含有0個(gè)元素,1個(gè)元素,…,m個(gè)元素，其方案種數(shù)恰為公式的左邊.mmmm01m

mkm-k

mmkk=02023/2/4組合數(shù)學(xué)665.

()+()+…+()=2,

組合證2

從(0,0)走m步有2m

種走法,都落在直線x+y=m上,而到(m,0),(m-1,1),(m-2,2),…,(2,m-2),(1,m-1),(0,m)各點(diǎn)的走法各有(

),(

),(

),…,(

),(

),()種mmmm01m

mmmmmm012m-2m-1m(m,0)(0,m)(m-1,1)2023/2/4組合數(shù)學(xué)676.()-()+()-…±()=0證1

在(x+y)=∑()xy中令x=1,y=-1即得.nnnn012nnn-kknk

nk=02023/2/4組合數(shù)學(xué)68證2

在[1,n]的所有組合中,含1的組合←→不含1的組合.有1—1對(duì)應(yīng)關(guān)系。在任一含1組合及與之對(duì)應(yīng)的不含1組合中，必有一奇數(shù)個(gè)元的組合與一偶數(shù)個(gè)元的組合。將含奇數(shù)個(gè)元的組合做成集，將含偶數(shù)個(gè)元的組合做成另一集。此二集的元數(shù)相等。 ∑(

)=∑(

)nniii奇i偶2023/2/4組合數(shù)學(xué)697.()=()()+()()+…+()()即Vandermonde恒等式證1

從m個(gè)互異紅球和n個(gè)互異藍(lán)球中取r個(gè)球,按r個(gè)球中紅球的個(gè)數(shù)分類.組合證法:(0,0)到(m+n-r，r)點(diǎn)的路徑.(0,0)→(m-r+l,r-l)→(m+n-r,r)

(

)()()=∑()()m+nmnmnmnr0r1r-1r0mnr-llm+nmnrr-llP(m-r,r)(m+n-r,r)(m-r+l,r-l)l=0,1,2,…,r

Q(m,0)

rl=02023/2/4組合數(shù)學(xué)70李善蘭(1811—1882），清代數(shù)學(xué)家李善蘭恒等式： ∑()()()=()()kln+k+l-jn+kn+ljjk+lklj≥0證：利用Vandermonde恒等式及

()()=()()=()() (接下頁)nvnn-pnn-pvppn-vpv-p2023/2/4組合數(shù)學(xué)71有∑()()()=∑()()(∑()())=∑()∑()()()=∑()∑()()()=∑()()()=∑()()()=()∑()()=()()kln+k+l-jjjk+lkln+kl-jjjk+vl-vn+kkll-jk+vjjl-vn+kklvk+vjvln+klk+vk+vvkn+knlkn-vvn+knlkn-vvn+kn+lkl

j≥0j≥0v≥jv≥0j≥0v≥0j≥0v≥0v≥0v≥02023/2/4組合數(shù)學(xué)72

五、多項(xiàng)式定理定理(多項(xiàng)式定理)：設(shè)n是正整數(shù)，x1,x2,…,xk是任意k個(gè)實(shí)數(shù)，則多重集｛n1·x1,n1·x2,…,nk·xk｝的全排列數(shù)？2023/2/4組合數(shù)學(xué)73證明:(x1+x2+…+xk)n是n個(gè)因子(x1+x2+…+xk)的乘積，其展開式中共有kn項(xiàng)。設(shè)是展開式中任一項(xiàng)，如果在中有n1個(gè)x1，n2個(gè)x2，…，nk個(gè)xk(n1+n2+…+nk=n)，則把歸于(n1,n2,…,nk)類。顯然，屬于(n1,n2,…,nk)類的項(xiàng)的個(gè)數(shù)等于因此展開式中的系數(shù)為2023/2/4組合數(shù)學(xué)74推理(二項(xiàng)式定理)：設(shè)n是正整數(shù)，x和y是任意實(shí)數(shù)，則例如：2023/2/4組合數(shù)學(xué)75求中x5的系數(shù)x5的系數(shù)為2023/2/4組合數(shù)學(xué)76令x=y=1，得到令x=-1和y=1得到2023/2/4組合數(shù)學(xué)77[例]求證：證明：（1）由于(1+x)n·(1+x)m=(1+x)n+m,則比較上式兩邊xr的系數(shù)，得：2023/2/4組合數(shù)學(xué)78（2）在（1）的式子中，令m=r=n，得即2023/2/4組合數(shù)學(xué)79[例]求證：證明：令則f(0)=0,利用冪級(jí)數(shù)的可導(dǎo)性2023/2/4組合數(shù)學(xué)80則上式兩邊積分得：所以從而2023/2/4組合數(shù)學(xué)81[例]求證：證明：證明：當(dāng)n=m時(shí)，結(jié)論成立。當(dāng)n>m時(shí)，2023/2/4組合數(shù)學(xué)82六、T路定義(T步)：在Oxy坐標(biāo)平面上，橫坐標(biāo)與縱坐標(biāo)都是整數(shù)的點(diǎn)稱為整點(diǎn)。由任一個(gè)整點(diǎn)(x,y)到整點(diǎn)(x+1,y+1)或(x+1,y-1)的有向線段稱為一個(gè)T步。(x,y)(x+1,y+1)(x+1,y-1)2023/2/4組合數(shù)學(xué)83定義(T路)：由整點(diǎn)A到整點(diǎn)B的一條T路是指由若干個(gè)T步組成的起點(diǎn)為A、終點(diǎn)為B的有向折線。A··

B并不是任意兩點(diǎn)之間都有T路·C·D2023/2/4組合數(shù)學(xué)84定理(T條件)：如果存在由整點(diǎn)A(a,α)到整點(diǎn)B(b,β)的T路，則①b>a,②b-a≥∣β－α∣，③a+α與b+β的奇偶性相同。（上述三個(gè)條件稱為T條件）A(a,α)··

B(b,β)2023/2/4組合數(shù)學(xué)85AB設(shè)A(a,α)，B(b,β)DC2023/2/4組合數(shù)學(xué)86設(shè)A(a,α)，B(b,β)XYO2023/2/4組合數(shù)學(xué)87定理(T路的計(jì)數(shù))：設(shè)整點(diǎn)A(a,α)與整點(diǎn)B(b,β)滿足T條件，則由A到B的T路的數(shù)目為：從A(2,1)到B(7,4)的T路數(shù)目為：由相等原則和格路計(jì)數(shù)公式：如從(0,0)到(6,2)到T路數(shù)：2023/2/4組合數(shù)學(xué)88A●●BA’●設(shè)A(a,α)，B(b,β),A’(a,-α)每一條從A到B且經(jīng)過x軸的T路，一一對(duì)應(yīng)一條從A’到B的T路2023/2/4組合數(shù)學(xué)89七、反射原理定理(反射定理)：設(shè)整點(diǎn)A(a,α)與整點(diǎn)B(b,β)滿足T條件，且α>0,β>0,b-a≥α+β，則由A到B且經(jīng)過x軸（即與x軸有交點(diǎn)）的T路的條數(shù)等于由A’(a,-α)到B的T路的條數(shù)，為：如：從(1,1)到(8,4)且經(jīng)過x軸到T路數(shù)：2023/2/4組合數(shù)學(xué)90定理：設(shè)整點(diǎn)A(a,α)與整點(diǎn)B(b,β)滿足T條件，且α>0,β>0,b-a≥α+β，則由A到B且不經(jīng)過x軸的T路的條數(shù)為：2023/2/4組合數(shù)學(xué)91[例]甲、乙兩人進(jìn)行乒乓球比賽，最后比分為21:17，求在比賽過程中的記分情形的種數(shù)。解：設(shè)所求為N。一種記分情形唯一確定了一個(gè)數(shù)列a1a2…a38，其中以Aj表示點(diǎn)(j,a1+a2+…+aj)(j=1,2,…,38)，則比賽記分情形可用有向折線表示。2023/2/4組合數(shù)學(xué)92所以N等于由點(diǎn)(1,1)到點(diǎn)(38,4)的T路的條數(shù)，為：又Aj+1與Aj(j=1,2,…,38)橫坐標(biāo)之差為1，縱坐標(biāo)之差為其值為1或-1，故是一個(gè)T步，從而是從A1(1,1)到A38(38,4)且不經(jīng)過x軸的T路。Aj●●

Aj+1●

Aj+12023/2/4組合數(shù)學(xué)93[例]甲、乙兩人進(jìn)行乒乓球比賽，最后比分為21:17，求在比賽過程中甲總是領(lǐng)先于乙的記分情形的種數(shù)。解：設(shè)所求為N。一種記分情形唯一確定了一個(gè)數(shù)列a1a2…a38，其中以Aj表示點(diǎn)(j,a1+a2+…+aj)(j=1,2,…,38)，則比賽記分情形可用有向折線表示。由于甲的得分始終高于乙，故Aj的縱坐標(biāo)大于零。又Aj+1與Aj(j=1,2,…,38)橫坐標(biāo)之差為1，縱坐標(biāo)之差為其值為1或-1，故是一個(gè)T步，從而是從A1(1,1)到A38(38,4)且不經(jīng)過x軸的T路。2023/2/4組合數(shù)學(xué)94所以N等于由點(diǎn)(1,1)到點(diǎn)(38,4)且不經(jīng)過x軸的T路的條數(shù)，為：2023/2/4組合數(shù)學(xué)9517.甲、乙兩人競(jìng)選廠長(zhǎng)，甲得選票a張，乙得選票b張，a>b，問在點(diǎn)票過程中甲的得票恒領(lǐng)先于乙的情形有多少種？解：用Aj(j=1,2,…,a+b)表示點(diǎn)(j,a1+a2+…+aj)，其中則滿足題意的點(diǎn)票過程可用有向折線表示。顯然，Aj(j=1,2,…,a+b)是整點(diǎn)。由于在點(diǎn)票過程中甲的得票恒領(lǐng)先于乙，故Aj的縱坐標(biāo)大于0，而Aj+1(j=1,2,…,a+b－1)與Aj的橫坐標(biāo)之差為1，縱坐標(biāo)之差為1或－1，故是一個(gè)T步，從而2023/2/4組合數(shù)學(xué)96

是由A1(1,1)到Aa+b(a+b,a-b)且不經(jīng)過x軸的一條T路。于是不同的點(diǎn)票情形的種數(shù)等于由整點(diǎn)(1,1)到整點(diǎn)(a+b,a-b)且不經(jīng)過x軸的T路的條數(shù)，為：2023/2/4組合數(shù)學(xué)97定理：(1)由點(diǎn)O(0,0)到點(diǎn)V(2n,0)，中途不經(jīng)過x軸且位于上半平面的T路的條數(shù)為：(2)由點(diǎn)O(0,0)到點(diǎn)V(2n,0)，且位于上半平面的T路的條數(shù)為：OV(2n,0)2023/2/4組合數(shù)學(xué)98定理：(1)由點(diǎn)O(0,0)到點(diǎn)V(2n,0)，中途不經(jīng)過x軸且位于上半平面的T路的條數(shù)為：(2)由點(diǎn)O(0,0)到點(diǎn)V(2n,0)，且位于上半平面的T路的條數(shù)為：OV(2n,0)xyX’O’2023/2/4組合數(shù)學(xué)99八、卡塔蘭(Catalan)數(shù)一個(gè)凸n＋1邊形,通過不相交于n＋1邊形的對(duì)角線,把n＋1邊形拆分成若干三角形,不同拆分的數(shù)目用Cn表之.例如五邊形有如下五種拆分方案，故C4＝52023/2/4組合數(shù)學(xué)100(n=1,2,…)稱為Catalan數(shù)。由前面的定理知，Cn也是由點(diǎn)O(0,0)到點(diǎn)V(2n,0)，中途不經(jīng)過x軸且位于上半平面的T路的條數(shù)。下面給出Catalan數(shù)的另外一種解釋：某種方程解的個(gè)數(shù)一般地：八、卡塔蘭(Catalan)數(shù)2023/2/4組合數(shù)學(xué)101定理：設(shè)S2n表示滿足條件的解(x1,x2,…,x2n)的集合，則定理：設(shè)T2n表示滿足條件的解(x1,x2,…,x2n)的集合，則2023/2/4組合數(shù)學(xué)102定理：設(shè)S2n表示滿足條件的解(x1,x2,…,x2n)的集合，則證明：用K表示從點(diǎn)A0(0,0)到點(diǎn)A2n(2n,0)，中途不經(jīng)過x軸且位于上半平面點(diǎn)全部T路的集合，則下面構(gòu)造K與S2n的一一對(duì)應(yīng)關(guān)系2023/2/4組合數(shù)學(xué)103設(shè)s∈S2n，且s=(x1,x2,…,x2n)。記

Aj(j,j-2x1-2x2-…-2xj)，依題意，Aj(j=1,2,…,2n)是整點(diǎn)且當(dāng)1≤j≤2n－1時(shí)，j-2x1-2x2-…-2xj>0，則Aj在x軸的上方。

又因?yàn)锳j+1與Aj的橫坐標(biāo)之差為1，縱坐標(biāo)之差為(j+1-2x1-2x2-…-2xj+1)-(j-2x1-2x2-…-2xj)=1-2xj+1,其值為1或－1，所以是一個(gè)T步。2023/2/4組合數(shù)學(xué)104

從而且ls由s唯一確定。作由S2n到K到映射顯然φ是一個(gè)從S2n到K到一一對(duì)應(yīng)映射。由相等原則，由2023/2/4組合數(shù)學(xué)105[例]甲、乙兩對(duì)進(jìn)行手球比賽，最后比分為20:20，求在比賽過程中甲隊(duì)總是領(lǐng)先于乙隊(duì)的記分情形的種數(shù)。解：設(shè)所求為N。比賽記分情形可用由0和1作成的長(zhǎng)為40的有序數(shù)組(x1,x2,…,x40)表示，其中依題意有所以N等于上述方程解的個(gè)數(shù)，為：2023/2/4組合數(shù)學(xué)106[例]甲、乙兩對(duì)進(jìn)行手球比賽，最后比分為20:20，求在比賽過程中甲隊(duì)總是不落后于乙隊(duì)的記分情形的種數(shù)。解：設(shè)所求為N。比賽記分情形可用由0和1作成的長(zhǎng)為40的有序數(shù)組(x1,x2,…,x40)表示，其中依題意有所以N等于上述方程解的個(gè)數(shù)，為：2023/2/4組合數(shù)學(xué)107第二部分

母函數(shù)與遞推關(guān)系2023/2/4組合數(shù)學(xué)108本章學(xué)習(xí)目的

掌握母函數(shù)的基本性質(zhì)，用普通型母函數(shù)解線性常系數(shù)遞推關(guān)系，用指數(shù)型母函數(shù)解某些與排列有關(guān)的計(jì)數(shù)問題，掌握根據(jù)實(shí)際問題列出遞推關(guān)系的技巧，掌握解某幾種非線性常系數(shù)遞推關(guān)系的方法。

2023/2/4組合數(shù)學(xué)109一、母函數(shù)

遞推關(guān)系是計(jì)數(shù)的一個(gè)強(qiáng)有力的工具，特別是在做算法分析時(shí)是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當(dāng)然母函數(shù)還有其他用處，但里這主要是介紹解遞推關(guān)系上的應(yīng)用。例如

項(xiàng)的系數(shù)中所有的項(xiàng)包括n個(gè)元素a1,a2,…an中取兩個(gè)組合的全體.2023/2/4組合數(shù)學(xué)110同理x3項(xiàng)系數(shù)包含了從n個(gè)元素a1，a2，…an中取3個(gè)元素組合的全體。以此類推……2023/2/4組合數(shù)學(xué)111

定義：對(duì)于序列構(gòu)造一函數(shù)：稱函數(shù)G(x)是序列的母函數(shù)。例如(1+x)n

是序列的母函數(shù)。

序列可記為。

如若已知序列則對(duì)應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則該序列也隨之確定。

2023/2/4組合數(shù)學(xué)112例：若有紅球一只，藍(lán)球、黑球各二只，試求有多少種不同的組合方案。除一個(gè)球也不取外：（1）取一個(gè)球：3種｛●，●，●｝（2）取兩個(gè)球：5種｛●●

，●●，●●，●●，●●｝（3）取三個(gè)球：5種｛●●

●

，●

●●，●●●

，●

●●，●●●

｝（4）取四個(gè)球：3種｛●●

●

●

，●●●●，●

●●●

｝（5）取五個(gè)球：1種｛●●

●

●●

｝總共17種組合。2023/2/4組合數(shù)學(xué)113

顯然，令Ci（i=0,1,2,3,4,5,）表示取i個(gè)求的組合數(shù)，則其對(duì)應(yīng)的母函數(shù)為：

G(x)＝1+3x+5x2+5x3+3x4+x5另外，我們注意到，設(shè)Gk(x)(k=1,2,3)分別表示只取紅、藍(lán)、黑球的組合數(shù)對(duì)應(yīng)的母函數(shù)，由于考慮同顏色的球是沒有區(qū)別的，則容易得到：

G1(x)=1+x,G2(x)=1+x+x2,G3(x)=1+x+x2G1(x)G2(x)G3(x)=(1+x)(1+x+x2)(1+x+x2)=(1+2x+2x2+x3)(1+x+x2)=1+3x+5x2+5x3+3x4+x5=G(x)推廣到一般？2023/2/4組合數(shù)學(xué)114例：某單位有2m位男員工，n位女員工。現(xiàn)在要成立一個(gè)由偶數(shù)個(gè)男員工和數(shù)目不少于兩個(gè)的女員工的小組，問有多少種組成方式？偶數(shù)個(gè)男員工的組合數(shù)對(duì)應(yīng)的母函數(shù)：

A(x)=C(2m,2)x2+C(2m,4)x4+…+C(2m,2m)x2m不少于兩個(gè)女員工的組合數(shù)對(duì)應(yīng)的母函數(shù)：

B(x)=C(n,2)x2+C(n,3)x3+…+C(n,n)xn問題對(duì)應(yīng)的母函數(shù)：

C(x)=A(x)B(x)C(X)的展開式的各系數(shù)之和即為所求組合數(shù)。2023/2/4組合數(shù)學(xué)1152023/2/4組合數(shù)學(xué)116[例]若有1克、2克、3克、4克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？解：對(duì)應(yīng)的母函數(shù)為：對(duì)應(yīng)項(xiàng)的系數(shù)即為所求。2023/2/4組合數(shù)學(xué)117[例]若有1克砝碼3枚、2克砝碼4枚、4克砝碼2枚，問能稱出那幾種重量？各有幾種方案？能稱出20種重量，方案數(shù)為60（系數(shù)之和）。2023/2/4組合數(shù)學(xué)118[例]若有1、2、4、8、16、32克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？

從生成函數(shù)可以得知，用這些砝碼可以稱出從0克到63克的重量，而且辦法都是唯一的。2023/2/4組合數(shù)學(xué)119二、 幾個(gè)常用的母函數(shù)

一個(gè)序列和它的母函數(shù)一一對(duì)應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。2023/2/4組合數(shù)學(xué)1202023/2/4組合數(shù)學(xué)121[例]寫出數(shù)列的母函數(shù)。解：數(shù)列的母函數(shù)2023/2/4組合數(shù)學(xué)122[例]求數(shù)列an=n(n+3)的母函數(shù)。解：數(shù)列對(duì)應(yīng)的母函數(shù)為：2023/2/4組合數(shù)學(xué)123[例]已知數(shù)列{an}的母函數(shù)為求數(shù)列{an}。解：由于所以2023/2/4組合數(shù)學(xué)124三、指數(shù)型母函數(shù)

定義：對(duì)于序列，函數(shù)稱為是序列的指數(shù)型母函數(shù)2023/2/4組合數(shù)學(xué)125兩個(gè)結(jié)論：(a)若元素a1

有n1個(gè)，元素a2有n2

個(gè)，……，元素ak有nk個(gè)，由此；組成的n個(gè)元素的排列，不同的排列總數(shù)為其中2023/2/4組合數(shù)學(xué)126

例1：求由兩個(gè)a，1個(gè)b，2個(gè)c組成的不同排列總數(shù)。

根據(jù)結(jié)論一，不同的排列總數(shù)為2023/2/4組合數(shù)學(xué)127

(b)若元素a1

有n1個(gè)，元素a2

有n2個(gè)，……，元素ak有nk個(gè)，由此；組成的n個(gè)元素中取r個(gè)排列，設(shè)其不同的排列數(shù)為pr，則序列p0，p1，…，pk的指數(shù)型母函數(shù)為2023/2/4組合數(shù)學(xué)128

例2：由1，2，3，4四個(gè)數(shù)字組成的五位數(shù)中，要求數(shù)1出現(xiàn)次數(shù)不超過2次，但不能不出現(xiàn)；2出現(xiàn)次數(shù)不超過1次；3出現(xiàn)次數(shù)可達(dá)3次，也可以不出現(xiàn)；4出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個(gè)數(shù)。

設(shè)滿足上述條件的r位數(shù)為，序列的指數(shù)型母函數(shù)為2023/2/4組合數(shù)學(xué)1292023/2/4組合數(shù)學(xué)130由此可見滿足條件的5位數(shù)共215個(gè)。2023/2/4組合數(shù)學(xué)131[例]求在多重集A=｛3a,2

b,3

c｝中選取4個(gè)進(jìn)行排列的不同方法種數(shù)。解：設(shè)從A中選取r個(gè)的排列種數(shù)為ar，則數(shù)列{ar}對(duì)應(yīng)的指數(shù)型生成函數(shù)為：所以a4＝702023/2/4組合數(shù)學(xué)132例3:求1，3，5，7，9五個(gè)數(shù)字組成的n位數(shù)的個(gè)數(shù)，要求其中3，7出現(xiàn)的次數(shù)為偶數(shù)，其他1，5，9出現(xiàn)次數(shù)不加限制。 設(shè)滿足條件的r位的個(gè)數(shù)為ar

，則序列a1,a2,a3,…對(duì)應(yīng)的指數(shù)型母函數(shù)為2023/2/4組合數(shù)學(xué)133由于2023/2/4組合數(shù)學(xué)1342023/2/4組合數(shù)學(xué)135利用遞推關(guān)系進(jìn)行計(jì)數(shù)是組合計(jì)數(shù)的一種常見方法，也是計(jì)算機(jī)科學(xué)中進(jìn)行算法設(shè)計(jì)與分析的重要工具。對(duì)數(shù)列{an},所謂遞推關(guān)系，就是數(shù)列的前后項(xiàng)之間的關(guān)系。如：（1）an=an-1+2,

（2）an-2an-1-an-2=0,

（3）an-4an-1=5n

四、遞推關(guān)系2023/2/4組合數(shù)學(xué)136[例]n條無三線共點(diǎn)直線將平面分成了多少個(gè)區(qū)域？設(shè)n條直線將平面分成了Dn個(gè)區(qū)域。先考慮n－1條直線將平面分成了Dn-1個(gè)區(qū)域，再將第n條直線加入，這時(shí)第n條直線被前n－1條直線分成了n段，這n段正好是新增加的n個(gè)區(qū)域的一邊界。所以Dn=Dn-1+n，其中D1=2。2023/2/4組合數(shù)學(xué)137

[例]漢諾(Hanoi)塔問題：這是個(gè)組合數(shù)學(xué)中的著名問題。n個(gè)圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個(gè)盤移到C柱上請(qǐng)?jiān)O(shè)計(jì)一種方法，并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只有A、B、C三根柱子可用。

ABCABC

初始狀態(tài)最終狀態(tài)2023/2/4組合數(shù)學(xué)138這是在十九世紀(jì)末，歐洲風(fēng)行的一種游戲。并大肆宣傳說，布拉瑪神廟的教士所玩的這種游戲結(jié)束之日就是世界毀滅之時(shí)。（為什么這樣說？）Hanoi問題對(duì)于計(jì)算機(jī)科學(xué)來說也是個(gè)典型的問題，解決問題的第一步要設(shè)計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，即估計(jì)工作量。

算法：N=2時(shí)

，先把上面的圓盤移到B上，再把下面的圓盤移到C上，最后把B上的圓盤移到C上，到此轉(zhuǎn)移完畢

。

移動(dòng)次數(shù)？一般地：2023/2/4組合數(shù)學(xué)139

假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定。先把上面的n-1個(gè)圓盤經(jīng)過C轉(zhuǎn)移到B，第二步把A下面一個(gè)圓盤移到C上，最后再把B上的n-1個(gè)圓盤經(jīng)過A轉(zhuǎn)移到C上

。

上述算法是遞歸的運(yùn)用。n=2時(shí)已給出算法；n=3時(shí)，第一步便利用算法把上面兩個(gè)盤移到B上，第二步再把第三個(gè)圓盤轉(zhuǎn)移到柱C上；最后把柱B上兩個(gè)圓盤轉(zhuǎn)移到柱C上。N=4，5，…以此類推。

2023/2/4組合數(shù)學(xué)140算法分析：令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到B上；然后把第n個(gè)盤子轉(zhuǎn)到C上；最后再一次將B上的n-1個(gè)盤子轉(zhuǎn)移到C上。

n=2時(shí)，算法是對(duì)的，因此，n=3是算法是對(duì)的。以此類推。于是有算法復(fù)雜度為：h(n)是n的指數(shù)函數(shù)，若n=60,260≈1.15292×1018，以一秒移動(dòng)一個(gè)圓盤的速度，則要移動(dòng)60個(gè)圓盤的Hanoi塔，需要2023/2/4組合數(shù)學(xué)141[例]10個(gè)數(shù)字(0到9)和4個(gè)四則運(yùn)算符(+,－,×,÷)組成的14個(gè)元素。求由其中