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

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

數(shù)

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

---恩格斯

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

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

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

---馬克思

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

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

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

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

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

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

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

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

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

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

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

胡錦濤同志在1998年接見"五四"青年獎章時發(fā)表的講話中指出，組合數(shù)學不同于傳統(tǒng)的純數(shù)學的一個分支，它還是一門應用學科，一門交叉學科。他希望中國的組合數(shù)學研究能夠為國家的經(jīng)濟建設服務。

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

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

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

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

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

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

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

] 設事件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ù)學18[例]

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

18+10=28人。[例]

北京每天直達上海的客車有5次，客機有3次，則每天由北京直達上海的旅行方式有

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

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

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

＝n(n-1)/2。解：當x＝1時，所有可能的有序對有n－1個；當x＝2時，所有可能的有序對有n－2個，…當x＝n－1時，所有可能的有序對有1個。2023/2/4組合數(shù)學20[乘法法則

] 設事件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ù)學21[例]

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

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

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

某種樣式的運動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍、橙、黃，條紋色可選黑、白，則共有

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

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

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

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

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

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

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

3！P（7，2）＝252。2023/2/4組合數(shù)學30[例]由5種顏色的星狀物，20種不同花排成如下的圖案：兩邊是星狀物，中間是3朵花。問有多少種這樣的圖案？解：設所求為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ù)學31[例]求20000到70000間的偶數(shù)中由不同數(shù)字組成的5位數(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ù)學32〔例〕求由n個相異元素a1，a2，…，an構成的a1與a2不相鄰的全排列的個數(shù)。解：n個元素的全排列種數(shù)為n！，其中a1與a2相鄰的全排列的個數(shù)為2(n-1)!，所以，滿足題意的全排列個數(shù)為：

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

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

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

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

3×64＝3888個。由加法原則：共有432＋3888＝4320個。2023/2/4組合數(shù)學35(三)多重集的排列定義（多重集）：由n1個a1，n2個a2，…，nk個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ù)學36定義（多重集的排列）：設

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

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

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

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

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

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

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

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

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

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

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

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ù)學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ù)學49[例]甲和乙兩單位共11個成員，其中甲單位7人，乙單位4人，擬從中組成一個5人小組：（1）若要求必須包含乙單位2人；（2）若要求至少包含乙單位2人；（3）若要求乙單位某一人與甲單位特定一人不能同時在這個小組。試分別求各有多少種方法。解：（1）（2）2023/2/4組合數(shù)學50（3）不妨設甲單位A與乙單位B不能同時在小組。首先A與B同時在小組的情形有所以所求為：2023/2/4組合數(shù)學51[例]

從[1,300]中取3個不同的數(shù)，使這3個數(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個數(shù)同屬于A;

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

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

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

由乘法原則得

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

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

設A＝{a1,a2,…,an}為n元集，則A的任一個r－可重復組合可表成{x1·a1,x2·a2,…,xn·an}，其中xi為非負整數(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的一個9-可重復組合。

問題：A的r－可重復組合的個數(shù)？2023/2/4組合數(shù)學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}中，可重復取6個的組合數(shù)為：2023/2/4組合數(shù)學56A={1,2,3,4,5}，取10-可重復組合：

{1，1，1，2，3，3，3，4，4，5}考慮:構造與此可重復組合對應的一個不可重復組合

{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}這個10-可重復組合相當于從

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

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作不允許重復的組合。2023/2/4組合數(shù)學58(三)組合的基本性質1.C(n,r)=C(n,n-r)

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

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ù)學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ù)學61由組合的計算公式：2023/2/4組合數(shù)學623.()+()+()+…+()=()[證明一]從[1,n+r+1]取a1a2…anan+1，設

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ù)學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ù)學644.()()=()()①選政治局,再選常委,n個中央委員選出m名政治局委員,再從其中選出k名常委②選常委,再選非常委政治局委員兩種選法都無遺漏,無重復地給出可能的方案，應該相等。nmnn-kmkkm-k2023/2/4組合數(shù)學655.

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

證1(x+y)

=∑(

)x

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

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

mkm-k

mmkk=02023/2/4組合數(shù)學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)各點的走法各有(

),(

),(

),…,(

),(

),()種mmmm01m

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

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

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

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

)=∑(

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

從m個互異紅球和n個互異藍球中取r個球,按r個球中紅球的個數(shù)分類.組合證法:(0,0)到(m+n-r，r)點的路徑.(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ù)學70李善蘭(1811—1882），清代數(shù)學家李善蘭恒等式： ∑()()()=()()kln+k+l-jn+kn+ljjk+lklj≥0證：利用Vandermonde恒等式及

()()=()()=()() (接下頁)nvnn-pnn-pvppn-vpv-p2023/2/4組合數(shù)學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ù)學72

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

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

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

Aj+1●

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

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

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

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

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

母函數(shù)與遞推關系2023/2/4組合數(shù)學108本章學習目的

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

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

遞推關系是計數(shù)的一個強有力的工具，特別是在做算法分析時是必需的。遞推關系的求解主要是利用母函數(shù)。當然母函數(shù)還有其他用處，但里這主要是介紹解遞推關系上的應用。例如

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

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

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

序列可記為。

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

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

，●●，●●，●●，●●｝（3）取三個球：5種｛●●

●

，●

●●，●●●

，●

●●，●●●

｝（4）取四個球：3種｛●●

●

●

，●●●●，●

●●●

｝（5）取五個球：1種｛●●

●

●●

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

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

G(x)＝1+3x+5x2+5x3+3x4+x5另外，我們注意到，設Gk(x)(k=1,2,3)分別表示只取紅、藍、黑球的組合數(shù)對應的母函數(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ù)學114例：某單位有2m位男員工，n位女員工。現(xiàn)在要成立一個由偶數(shù)個男員工和數(shù)目不少于兩個的女員工的小組，問有多少種組成方式？偶數(shù)個男員工的組合數(shù)對應的母函數(shù)：

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

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

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

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

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

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

有n1個，元素a2有n2

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

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

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

(b)若元素a1

有n1個，元素a2

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

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

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

b,3

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

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

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

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

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

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

ABCABC

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

算法：N=2時

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

。

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

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

。

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

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

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