第一章排列與組合

2024/10/291組合數學郝聚濤haojutao163計算機系2024/10/29組合數學-上海理工大學2教材組合數學（第四版），盧開澄盧華明著，清華大學出版社，2019本書共分8章，內容包括:排列與組合遞推關系與母函數容斥原理與鴿巢原理Burnside引理與Polya定理區(qū)組設計線性規(guī)劃編碼簡介組合算法簡介考試

時間：第九周課內形式：閉卷內容：上課例題為主成績：平時+試卷成績2024/10/29組合數學-上海理工大學32024/10/29組合數學-上海理工大學41666年萊布尼茲所著《組合學論文》一書問世，這是組合數學的第一部專著。書中首次使用了組合論（Combinatorics）一詞。1646.7.1.—1716.11.14.）德國最重要的自然科學家、數學家、物理學家、歷史學家和哲學家，一個舉世罕見的科學天才，和牛頓同為微積分的創(chuàng)建人。1664年1月，萊布尼茨完成了論文《論法學之艱難》，獲哲學碩士學位。1665年，萊布尼茨向萊比錫大學提交了博士論文《論身份》，1666年，審查委員會以他太年輕(年僅20歲)而拒絕授予他法學博士學位，1667年2月，阿爾特多夫大學授予他法學博士學位，還聘請他為法學教授。1700年2月，他還被選為法國科學院院士。至此，當時全世界的四大科學院：英國皇家學會、法國科學院、羅馬科學與數學科學院、柏林科學院都以萊布尼次作為核心成員。2024/10/29組合數學-上海理工大學5始創(chuàng)微積分高等數學上的眾多成就

計算機科學貢獻1673年萊布尼茨特地到巴黎去制造了一個能進行加、減、乘、除及開方運算的計算機率先為計算機的設計，系統(tǒng)提出了二進制的運算法則，為計算機的現代發(fā)展奠定了堅實的基礎

豐碩的物理學成果

充分地證明了“永動機是不可能”的觀點哲學貢獻單子論多才多藝

1693年，萊布尼茨發(fā)表了一篇關于地球起源的文章，后來擴充為《原始地球》一書1677年，他寫成《磷發(fā)現史》，對磷元素的性質和提取作了論述在氣象學方面。他曾親自組織人力進行過大氣壓和天氣狀況的觀察1691年，萊布尼茨致信巴本，提出了蒸汽機的基本思想。1677年，萊布尼茨發(fā)表《通向一種普通文字》，以后他長時期致力于普遍文字思想的研究，對邏輯學、語言學做出了一定貢獻。今天，人們公認他是世界語的先驅……2024/10/29組合數學-上海理工大學6組合數學概述組合數學（combinatorialmathematics），又稱為離散數學。狹義的組合數學主要研究滿足一定條件的組態(tài)（也稱組合模型）的存在、計數以及構造等方面問題。組合數學主要內容有組合計數、組合設計、組合矩陣、組合優(yōu)化等。組合數學是計算機出現以后迅速發(fā)展起來的一門數學分支。計算機科學即算法的科學，而計算機所處理的對象是離散的數據，所以離散對象的處理就成了計算機科學的核心，而研究離散對象的科學恰恰就是組合數學。2024/10/29組合數學-上海理工大學7典型問題地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論的問題。船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運過河。只要船夫不在場，羊就會吃白菜、狼就會吃羊。船夫的船每次只能運送一種東西。怎樣把所有東西都運過河？這是線性規(guī)劃的問題。中國郵差問題：由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項式復雜度算法：先求出度為奇數的點，用匹配算法算出這些點間的連接方式，然后再用歐拉路徑算法求解。這也是圖論的問題。任務分配問題（也稱婚配問題）：有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？這是線性規(guī)劃的問題。2024/10/29組合數學-上海理工大學8第一章排列與組合主要內容：一、排列與組合二、排列組合的生成算法三、組合意義的解釋與應用舉例2024/10/29組合數學-上海理工大學9一、排列與組合

加法法則和乘法法則

一一對應

排列、組合

圓周排列

可重排列

可重組合

不相鄰的組合2024/10/29組合數學-上海理工大學101.加法法則與乘法法則加法法則：設具有性質A的事件有m個，具有性質B的事件有n個，則具有性質A或B的事件有m+n個。若

|A|=m,|B|=n,A∩B=,則

|A∪B|=m+n

。集合論語言：基本假設：性質A和性質B是無關的兩類。2024/10/29組合數學-上海理工大學11例1

某班選修企業(yè)管理的有18人，不選的有10人，則該班共有18+10=28人。例2

假設要從北京坐飛機或者火車或者客車到上海。北京每天到達上海的飛機有5個航班，火車有7趟，客車有10趟，則每天由北京到達上海的旅行方式有5+7+10=22種。2024/10/29組合數學-上海理工大學12乘法法則：設具有性質A的事件有m個，具有性質B的事件有n個，則具有性質A和B的事件有mn個。若

|A|=m,|B|=n,A

B={(a,b)|a

A,b

B},則

|A

B

|=mn

。集合論語言：例3從A到B有三條道路，從B到C有兩條道路，則從A經B到C有32=6

條道路。加法法則：得到事件通過兩種不同的方法。乘法法則：得到事件通過兩個步驟。2024/10/29組合數學-上海理工大學13例4

某種樣式的運動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍、橙、黃四種顏色的話，則方案數就不是44=16，而只有43=12種。2024/10/29組合數學-上海理工大學14例5(1)求小于10000的含1的正整數的個數；

(2)求小于10000的含0的正整數的個數。(1)小于10000的不含1的正整數可看做4位數，但

0000除外.故有9×9×9×9－1＝6560個。含1的有：9999－6560=3439個，

另：全部4位數有104個，不含1的四位數有94個，含1的4位數為兩個的差：104－94=3439個。2024/10/29組合數學-上海理工大學159999－7380=2619.9+9+9+9=(9－1)/(9－1)=73802345(2)“含0”和“含1”不可直接套用。0019含1但不含0。不含0的1位數有9個，2位數有92個，3位數有93個，4位數有94個。不含0小于10000的正整數有含0小于10000的正整數有2024/10/29組合數學-上海理工大學164×3×5＝60；(2)6×3＝18個位數有5種取法，千位數有8種取法，百位，十位各有8，7種取法。5×8×8×7＝2240。例6(1)n=73*112*134，求除盡n的數的個數；(2)n=73*142，求除盡n的數的個數；例7

在1000和9999之間有多少每位上的數字均不同的奇數？2024/10/29組合數學-上海理工大學17例8

由a,b,c,d,e這5個字符，從中取6個構成字符串，要求(1)第1，6個字符必為子音字符b，c，d；(2)每個字符串必有兩個母音字符a或e，且兩個母音字符不相鄰；(3)相鄰的兩個子音字符必不相同。求滿足這樣的條件的字符串的個數。由條件(1)，兩個母音字符的位置不能在1，6，又由條件(2)，位置只能是(2,4),(2,5)和(3,5)之一。對每種格式，母音2×2，相鄰子音3×2，其他兩個子音3×3。因此答案為

3×（2×2×3×2×3×3）=648。課堂練習2024/10/29組合數學-上海理工大學18abcde1b/c/d32a/e23b/c/d34a/22526b/c/d31b/c/d3223a/e24a/b/c35a/e26b/c/d31b/c/d32a/e23b/c/d3425a/e26b/c/d32024/10/29組合數學-上海理工大學19如我們說A集合有n個元素|A|=n，無非是建立了將A中元與[1,n]元一一對應的關系。在組合計數時往往借助于一一對應實現模型轉換。比如要對A集合計數，但直接計數有困難，于是可設法構造一易于計數的B，使得A與B一一對應。2.一一對應“一一對應”概念是一個在計數中極為基本的概念。一一對應既是單射又是滿射。2024/10/29組合數學-上海理工大學20一種常見的思路是按輪計場，費事。另一種思路是淘汰的選手與比賽(按場計)集一一對應。99場比賽。例9

在100名選手之間進行淘汰賽(即一場的比賽結果，失敗者退出比賽),最后產生一名冠軍，問要舉行幾場比賽？2024/10/29組合數學-上海理工大學21可以先計算對角線的個數，然后計算交點，但是存在在多邊形內無交點的情形，比較復雜?？梢钥紤]對應關系：多邊形內交點to多邊形四個頂點?？梢宰C明這是一一映射（映射，單且滿）。例10

設凸n邊形的任意三條對角線不共點，求對角線在多邊形內交點的個數。2024/10/29組合數學-上海理工大學22

一一對應例

CnH2n+2是碳氫化合物,隨著n的不同有下列不同的枝鏈：

H|H—C—H|H

H|H—C—H|H—C—H|H

H|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷2024/10/29組合數學-上海理工大學23

一一對應

H|H—C—H|H—C—H|H—C—H|H—C—H|H

H|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4異丁烷這說明對應CnH2n+2的枝鏈是有3n+2個頂點的一棵樹，其中n個頂點關聯(lián)的邊數為4；其它2n+2個頂點是葉子。對于這樣結構的每一棵樹，就對應有一種特定的化合物。構造化合物轉化為圖論問題，計算符合上述條件的樹的數目，便可確定對應的不同化合物的數目2024/10/29組合數學-上海理工大學241.2一一對應例

(Cayley定理)n個有標號的頂點的樹的數目等于

。兩個頂點的樹是唯一的。1－2n＝3時，數的數目3。1－2－3，1－3－2，2－1－3思路：n點樹《一一對應》長度n-2序列n個字母的長度n-2序列的數目是2024/10/29組合數學-上海理工大學25

一一對應⑦⑥

|

|②—③—①—⑤—④41253逐個摘去標號最小的葉子，葉子的相鄰頂點(不是葉子，是內點)形成一個序列，序列的長度為n-2例給定一棵有標號的樹邊上的標號表示摘去葉的順序。(摘去一個葉子相應去掉一條邊)

第一次摘掉②，③為②相鄰的頂點，得到序列的第一個數3

以此類推，消去23465，得到序列31551,長度為7－2=5，這是由樹形成序列的過程。2024/10/29組合數學-上海理工大學26

一一對應（復雜）由序列形成樹的過程：由序列31551得到一個新序列111233455567生成的過程是首先將31551排序得到11355，因為序列31551的長度為5，得到按升序排序的序列1234567，序列的長度為5+2(即n)，然后將11355按照大小插入到序列1234567中，得到111233455567然后將兩個序列排在一起315511112334555672024/10/29組合數學-上海理工大學27一一對應

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推導：將上下兩個序列同時去掉上行序列的第一個元素3(用藍色表示)，去掉下行序列的第一個無重復的元素2(用紅色表示)。生成一條邊(②—③)。由上序列確定3（藍色），再確定2（紅色），在下序列最小無重元，于是生成邊23。（并消除紅藍色點。）依此類推，減到下面剩最后兩個元素，這兩個元素形成最后一條邊。最后形成樹。（生成邊的序列23，13，45，56，15，17）2024/10/29組合數學-上海理工大學281.2一一對應上述算法描述：給定序列b=(b1b2…bn-2)設a=(123…n-1n)將b的各位插入a,得a’,對()做操作。a’是2n-2個元的可重非減序列。ba’操作是從a’中去掉最小無重元，設為a1,再從b和a’中各去掉一個b中的第一個元素，設為b1，則無序對(a1,b1)是一條邊。重復這一操作，得n-2條邊，最后a’中還剩一條邊，共n-1條邊，正好構成一個樹。b中每去掉一個元，a’中去掉2個元。2024/10/29組合數學-上海理工大學291.2一一對應由算法知由樹T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一對應。由序列確定的長邊過程是不會形成回路的。因任意長出的邊(u,v)若屬于某回路，此回路中必有一條最早生成的邊，不妨就設為(u,v)，必須使u,v都在長出的邊中重復出現，但照算法u,v之一從下行消失，不妨設為u，從而不可能再生成與u有關的邊了，故由()得到的邊必構成一個n個頂點的樹。ba’2024/10/29組合數學-上海理工大學30證明23

1

5

511

23

456

7

第一個不出現在上面的數2-3

3-1

4-56-55-11-7⑦⑥

|

|②—③—①—⑤—④2024/10/29組合數學-上海理工大學311.2一一對應證由一棵n個頂點的樹可得到一個長度為n－2的序列，且不同的樹對應的序列不同，因此。對n用歸納法可證反之，由一個長度為n－2的序列(每個元素為1~n的一個整數)，可得到一棵樹，且不同的序列對應的樹是不同的，因此 2024/10/29組合數學-上海理工大學32排列的典型例子是取球模型：從n個不同的球中,取出r個,放入r個不同的盒子里，每盒1個。第1個盒子有n種選擇,第2個有n-1種選擇，······，第r個有n-r+1種選擇。故由乘法法則有3.排列、組合定義：從n個不同的元素中，取r個不重復的元素，按次序排列，稱為從n個中取r個的無重排列。排列的個數用P(n,r)表示。當r=n

時稱為全排列。P(n,r)=n(n-1)······(n-r+1)=n!/(n-r)!P(n,n)=n!2024/10/29組合數學-上海理工大學33例11

由5種顏色的星狀物，20種不同的花排列成如下圖案：兩邊是星狀物，中間是3朵花，問共有多少種這樣的圖案？兩邊是星狀物，從五種顏色的星狀物中取兩個的排列的排列數是P(5,2)=20。20種不同的花取3種排列的排列數是根據乘法法則得圖案數為P(20,3)=20×19×18=6840。20×6840=136800。2024/10/29組合數學-上海理工大學34接上例，若A單位的2人排在隊伍兩端，B單位的3人不能相鄰，問有多少種不同的排列方案？(練習)B單位3人按一個元素參加排列，P(8,8)×P(3,3)。

A單位的人排法固定后A*A*A*A*A*A*A，B單位第一人有6種選擇，第二人有5種，第三人有4種，因此答案為P(7,7)×6×5×4。例12

A單位有7名代表，B單位有3位代表，排成一列合影要求B單位的3人排在一起，問有多少種不同的排列方案。2024/10/29組合數學-上海理工大學35例13

試求由{1,3,5,7}組成的所有不重復出現的整數的總和。這樣的整數可以是1位數,2位數,3位數,4位數，若設是i位數的總和，則S=S1+S2+S3+S4,S1=1+3+5+7=16；于是我們只需要計算Si即可。2024/10/29組合數學-上海理工大學36S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=96000+9600+960+96=106656；S=16+528+10656+106656=117856。

S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528；S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656；2024/10/29組合數學-上海理工大學37組合的個數用C(n,r)

表示。或者用表示。定義：從

n個不同元素中取

r個不重復的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合。C(n,r)=0，若n<r。2024/10/29組合數學-上海理工大學38故有C(n,r)·r!=P(n,r)，C(n,r)=P(n,r)/r!，從n個不同的球中,取出r個,放入r個相同的盒子里,每盒1個，這是從n個中取r個的組合的模型。若放入盒子后再將盒子標號區(qū)別，則又回到排列模型。每一個組合可有r!個標號方案。2024/10/29組合數學-上海理工大學39(2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76；(1)5×7+5×10+7×10=155;(3)155+76=231=C(5+7+10,2)。例14

有5本不同的日文書，7本不同的英文書，10本不同的中文書。(1)取2本不同文字的書；(2)取2本相同文字的書；(3)任取兩本書。2024/10/29組合數學-上海理工大學40例15

甲和乙兩單位共11個成員，其中甲單位7人，乙單位4人，擬從中組成一個5人小組：(1)要求包含乙單位恰好2人；(2)要求至少包含乙單位2人；(3)要求乙單位某一人與甲單位特定一人不能同時在這個小組。試求各有多少種方案。(1)C(4,2)×C(7,3)；(2)C(4,2)×C(7,3)+C(4,3)×C(7,2)+C(4,4)×C(7,1)；(3)C(10,5)+C(9,4)，或C(11,5)-C(9,3)。2024/10/29組合數學-上海理工大學41將[1,300]分成3類：A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡3(mod3)}={3,6,9,…,300}。例16

從[1,300]中取3個不同的數，使這3個數的和能被3整除，有多少種方案？（練習）要滿足條件，有四種情形：1.3個數同屬于A;2.3個數同屬于B;3.3個數同屬于C;4.A,B,C各取一數。故共有3C(100,3)+1003=485100+1000000=1485100。2024/10/29組合數學-上海理工大學42解1：a1選擇其同伴有7種可能，選定后,余下6人中某一人選擇其同伴只有5種可能，余下4人，其中某1人有3種選擇可能，在余下的2人只好配成一對，無法選擇，故共有N=7×5×3=105。例17

假定有a1,a2,a3,a4,a5,a6,a7,a8這8位成員，兩兩配對分成4組，試問有多少種方案？（練習）2024/10/29組合數學-上海理工大學43解2：分成4組。第一組取法為C(8,2)，余下6人，第二組取法為C(6,2)，第三組取法為C(4,2)，剩下為第四組。但4組的順序是重復的，因此答案為

C(8,2)×C(6,2)×C(4,2)/P(4,4)=105。解3：8人全排列有P(8,8)。分成4組。每組中2人交換是重復的，重復數為2×2×2×2，另外4組的順序也是重復的，重復數為P(4,4)，因此答案為

P(8,8)/(2×2×2×2×P(4,4))=105。2024/10/29組合數學-上海理工大學44一個進站方案可以表示成：00011001010100，其中“0”表示車，“1”表示間隔。其中“0”是不同元，“1”是相同元。給“1”這6個入口只用5個間隔。任意進站方案可表示成上面14個元素的一個排列。例18

某廣場有6個入口，每個入口每次只能通過一輛汽車，現有9輛車要開進廣場，有多少種入場方案？2024/10/29組合數學-上海理工大學45解2：在14個元的排列中先確定“1”的位置，有C(14,5)種選擇，再確定車的位置，有9！種選擇。故C(14,5)·9!即為所求。解3：實際上相當于14個位置中選取9輛汽車的排列，即為P(14,9)。解1：標號可產生5!個14個元的全排列。若設x為所求方案，則x·5!=14!。故

x=14!/5!=726485760。2024/10/29組合數學-上海理工大學46注意到，每個交點只有兩個對角線通過，對應了4個頂點所組成的一個組合，不同的交點對應的組合也不相同。故共有C(n,4)個交點。例19

一個凸n邊形，它的任何3條對角線都不交于同一點，問它的所有對角線在凸n邊形內部有多少個交點。2024/10/29組合數學-上海理工大學47定義：從n個不同的數中不重復的取出取出r個沿一圓周排列，稱為一個圓周排列。所有的r-圓周排列數記為Q(n,r)（計算公式？）。注意圓周排列與排列的不同之處在于圓周排列首尾相鄰。如a、b、c、d的4種不同排列

abcd,dabc,cdab,bcda,在圓周排列中都是一個排列。4.圓周排列2024/10/29組合數學-上海理工大學48124

31234124

32341124

33412124

34123以4個元素為例Q(n,r)=P(n,r)/r,2≤r≤nQ(n,n)=(n-1)!從n

個中取r

個的圓周排列的排列數為：2024/10/29組合數學-上海理工大學49若無要求，則為Q(8,8)；若要求藍色珠子一起，則為Q(6,6)×P(3,3)；若要求藍色珠子不相鄰，則為Q(5,5)×5×4×3。例205顆紅珠子，3顆藍珠子裝在圓板的四周，試問有多少種方案？若要求藍色珠子不相鄰，又有多少種排列方案？藍色珠子在一起呢？2024/10/29組合數學-上海理工大學50例215對夫婦出席一個宴會，圍一圓桌坐下，試問有幾種不同的坐法？要求每對夫婦相鄰又如何？若無限制，則為Q(10,10)；若要求相鄰，則為Q(5,5)×2×2×2×2×2。2024/10/29組合數學-上海理工大學51選取的r個元素叫做S的一個r-(可重)排列。當時也叫做S

的一個排列。定義：從一個多重集

中有序5.可重排列定義：多重集是指元素可以多次出現的集合，即元素可以重復。我們把某個元素ai出現的次數ni(ni=0,1,2,…)叫做該元素的重復數。通常把含有k種不同元素的多重集S記作2024/10/29組合數學-上海理工大學52定理：設多重集則S的r-(可重)排列數是kr。推論：設多重集且對一切的i=1,2,…k，有ni≥r，則S

的r-(可重)排列數是kr。2024/10/29組合數學-上海理工大學53所求的標