第一章 排列與組合

1、桂林理工大學(xué)理學(xué)院桂林理工大學(xué)理學(xué)院 謝海謝海研究生課程研究生課程組合數(shù)學(xué)組合數(shù)學(xué)課程簡介課程簡介 本課程針對計算機(jī)科學(xué)中的一個重要學(xué)本課程針對計算機(jī)科學(xué)中的一個重要學(xué)科科組合數(shù)學(xué)，組合數(shù)學(xué)是數(shù)學(xué)的一個分組合數(shù)學(xué)，組合數(shù)學(xué)是數(shù)學(xué)的一個分支，它研究事物在結(jié)定模式下的配置，研究支，它研究事物在結(jié)定模式下的配置，研究這種配置的存在性，所有可能配置的計數(shù)和這種配置的存在性，所有可能配置的計數(shù)和分類以及配置的各種性質(zhì)。組合數(shù)學(xué)在計算分類以及配置的各種性質(zhì)。組合數(shù)學(xué)在計算機(jī)科學(xué)中有著極其廣泛的應(yīng)用。機(jī)科學(xué)中有著極其廣泛的應(yīng)用。 組合學(xué)問題求解方法層出不窮、干變?nèi)f組合學(xué)問題求解方法層出不窮、干變?nèi)f化，應(yīng)以理

2、解為基礎(chǔ)，善于總結(jié)各種技巧，化，應(yīng)以理解為基礎(chǔ)，善于總結(jié)各種技巧，掌握科學(xué)的組織和推理方法。掌握科學(xué)的組織和推理方法。 組合數(shù)學(xué)是一個古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方.前言前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。519372486 1666年萊布尼茲所著組合學(xué)論文一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。 組合數(shù)學(xué)是一個迷人的數(shù)學(xué)分支, 它起源于古代的游戲和美學(xué)鑒賞. 在現(xiàn)代科學(xué)技術(shù)的發(fā)展中, 人們會面臨各種各樣的組合數(shù)學(xué)問題. 組合數(shù)學(xué)在計算機(jī)

3、科學(xué)中發(fā)揮著出極為重要的作用. 組合數(shù)學(xué)的蓬勃發(fā)展則是在計算機(jī)問世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對照。組合數(shù)學(xué)的基本內(nèi)容組合數(shù)學(xué)的基本內(nèi)容 組合數(shù)學(xué)關(guān)心的事情是要按照一定方式 “配置”一組事物，主要考慮以下幾方面的問題。存在性：(2) 計數(shù)與分類：主要內(nèi)容(3) 構(gòu)造算法：部分內(nèi)容(1) (4) 算法優(yōu)化： 如果人們想把有限多個對象按照它們所應(yīng)滿足的條件來進(jìn)行安排，當(dāng)符合要求的安排并非顯然存在或顯然不存在時，首要的問題就是要證明或者否定它的存在。這就是存在性問題存在性問題。如果所要求的安排存在，則可能

4、有多種不同的安排，這又經(jīng)常給人們提出這樣的問題：有多少種可能的安排方案？如何對安排的方案進(jìn)行分類？這就是計數(shù)問題計數(shù)問題。如果一個組合問題有解，則往往需要給出求其某一特定解的算法，這就是所謂的構(gòu)造性問題構(gòu)造性問題。如果算法很多，就需要在一定的條件下找出一個或者幾個最優(yōu)或近乎最優(yōu)的安排方案，這就是優(yōu)化問題優(yōu)化問題。 組合數(shù)學(xué)研究的組合數(shù)學(xué)研究的中心問題中心問題是按照一定的規(guī)則來是按照一定的規(guī)則來安排有限多個對象。安排有限多個對象。 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計數(shù)時的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。內(nèi)容：排

5、列與組合，遞推關(guān)系與母函數(shù)，內(nèi)容：排列與組合，遞推關(guān)系與母函數(shù)， 容容 斥原理與鴿巢原理，斥原理與鴿巢原理， Burnside引理與引理與 Plya定理定理 意義：方法意義：方法(用于編程用于編程), 素質(zhì)素質(zhì)(全面，細(xì)致全面，細(xì)致)難點：方法的應(yīng)用難點：方法的應(yīng)用, 例題的題型和思路例題的題型和思路教材：盧開澄教材：盧開澄 盧華明編著盧華明編著 組合數(shù)學(xué)（第組合數(shù)學(xué)（第4版）版） 清華大學(xué)出版社清華大學(xué)出版社講課：聽課為主講課：聽課為主, 課件較完整課件較完整, 板書和說明板書和說明 多種思路的分析，實例的直觀理解多種思路的分析，實例的直觀理解使用教材：使用教材：第一章第一章 排列組合排列組

6、合1.1 加法法則與乘法法則加法法則與乘法法則加法法則加法法則 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。集合論語言：若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。乘法法則乘法法則 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有 m n種產(chǎn)生方式。集合論語言：若 |A| = m ，|B| = n，AB = (a,b) | a A,b B，則 |A B| = m n 。 例例1-1 某種樣式的運動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案

7、。 若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。 在乘法法則中要注意事件事件 A 和和 事件事件 B 的相的相互獨立性互獨立性。另: 全部4位數(shù)有 個，不含1的四位數(shù)有 個，含1的4位數(shù)為兩個的差: 。 要點：含要點：含1的總數(shù)不含的總數(shù)不含1的的49343991044410例例1-2 1)求小于10000的含1的正整數(shù)的個數(shù)； 2)求小于10000的含0的正整數(shù)的個數(shù)。解：1)小于10000的不含1的正整數(shù)可看做4位數(shù)，但0000除外。 故有999916560個。 含1的有：99996560=3439個。1)小于100

8、的不含1的正整數(shù)可看做2位數(shù)，但00除外。 故有99180個。(00,02,09, 20,22,29, 30,99) 含1的有：9980=19個(01,11,21,91, 10,12,13,19)2)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含1但不含0。 直接套用直接套用, 含含0的的(?)有：有：9980=19個個 (00,10,20,90, 01,02,03,09) 其中其中:黃色黃色的的10個不是含個不是含0的。的。因此因此,修改計算方法為修改計算方法為: 不含不含0的的1位數(shù)有位數(shù)有9個，個，(1,2,9) 2位數(shù)有位數(shù)有 個，個，(11,12,19, 21,99)

9、不含不含0小于小于100的正整數(shù)有的正整數(shù)有81+9=90 含含0小于小于100的正整數(shù)有的正整數(shù)有9990=9個個 (10,20,90) 292)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含1但不含0。 在組合的習(xí)題中有許多類似的在組合的習(xí)題中有許多類似的隱含規(guī)定規(guī)定，要特別留神。，要特別留神。 不含不含0的的1位數(shù)有位數(shù)有9個，個，2位數(shù)有位數(shù)有 個，個，3位數(shù)有位數(shù)有 個，個，4位數(shù)有位數(shù)有 個個 不含不含0小于小于10000的正整數(shù)有的正整數(shù)有 含含0小于小于10000的正整數(shù)有的正整數(shù)有 99997380=2619個個39297380) 19/() 19(99995

10、43249n2例例1-3 長度為n的0，1符號串的數(shù)目為 。例如：n3，有8個 000,001,010,011,100,101,110,111。個nninniaaaaa2222., 2 , 1,1 , 0,21解：設(shè)由乘法規(guī)則, 40, 20, 30lllll60534除盡n的整數(shù)的個數(shù)是42313117n例例1-4 求除盡n的整數(shù)的個數(shù)。解：除盡n的整數(shù)是例例1-51-5 有a,b,c,d,e這5個字,從中取6個構(gòu)成一組字符串，要求: (1)第1個和第6個必須是子音b,c,d；(2)每一字符串必有a,e兩個母音，且a,e不相鄰；(3)相鄰兩子音不允許相同。求字符串?dāng)?shù)

11、目。解:格式(2,4): 子 母 子 母 子 子 格式(2,5): 子 母 子 子 母 子 格式(3,5): 子 子 母 子 母 子 格式(2,4): 格式(2,5): 格式(3,5):333333232332232332232323232323注意：條件(2)應(yīng)改為：每個字符串恰好有不相鄰的兩位是母音a或e。否則，理解為這兩位分別為a和e。64823333 由加法法則：例例1-61-6 有5本不同的日文書，7本不同的英文書，10本不同的中文書。1)取2本不同文字的書；2)取2本相同文字的書；3)任取兩本書。解：解： 注意：加法和乘法 1) 57+510+710=155; 2) C(5,2)+

12、C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231= =C(5+7+10,2)=C(22,2) 1.2 一一對應(yīng)一一對應(yīng) “一一對應(yīng)一一對應(yīng)”概念是一個在計數(shù)中極為基本的概念。一一對應(yīng)既是單射又是滿射。 如我們說A集合有n個元素 |A|=n，無非是建立了將A中元與1,n元一一對應(yīng)的關(guān)系。 在組合計數(shù)時往往借助于一一對應(yīng)實現(xiàn)模型轉(zhuǎn)換。 比如要對A集合計數(shù)，但直接計數(shù)有困難，于是可設(shè)法構(gòu)造一易于計數(shù)的B，使得A與B一一對應(yīng)。 例例1-7 CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈： H |H C H | H H |H C H |H C H | H H

13、 |H C H |H C H |H C H | Hn=1甲烷 n=2 乙烷 n=3 丙烷 H |H C H |H C H |H C H |H C H | H H | HH C H | |H C C H | |H C H | H Hn=4 丁烷 n=4異丁烷 這說明對應(yīng)CnH2n+2的枝鏈?zhǔn)怯?n+2個頂點的一棵樹，其中n個頂點關(guān)聯(lián)的邊數(shù)為4；其它2n+2個頂點是葉子。 對于這樣結(jié)構(gòu)的每一棵樹，就對應(yīng)有一種特定的化合物。 從而可以通過研究具有上述性質(zhì)的樹找到不同的碳?xì)浠衔顲nH2n+2。 例例1-8 在100名選手之間進(jìn)行淘汰賽(即一場的比賽結(jié)果，失敗者退出比賽)，最后產(chǎn)生一名冠軍，問要舉行幾

14、場比賽？ 解：解：一種常見的思路是按輪計場，費事。 各輪場數(shù)502512632199 剩余選手?jǐn)?shù)目：25, 13, 7, 4, 2, 1 另一種思路是淘汰的選手與比賽(按場計)集一一對應(yīng)。99場比賽。 例例1- 9 (Cayley定理定理) n個有標(biāo)號的頂點的樹的數(shù)目等于 。2nn解：兩個頂點的樹是唯一的。12 n3時，數(shù)的數(shù)目3。 123，132，2132nn思路：思路：n點樹 一一對應(yīng)一一對應(yīng) 長度n-2序列， n個字母的長度n-2序列的數(shù)目是 。逐個摘去標(biāo)號最小的葉子，葉子的相鄰頂點(不是葉子，是內(nèi)點)形成一個序列，序列的長度為n-2 | | 41 2 5 3給定一棵有標(biāo)號的樹邊上的標(biāo)號

15、表示摘去葉的順序。(摘去一個葉子相應(yīng)去掉一條邊) 第一次摘掉，為相鄰的頂點，得到序列的第一個數(shù)3，以此類推，消去23465，得到序列31551，長度為72 = 5，這是由樹形成序列的過程。 由序列形成樹的過程：由序列形成樹的過程：由序列31551得到一個新序列111233455567生成的過程是首先將31551排序得到11355，因為序列31551的長度為5，得到按升序排序的序列1234567，序列的長度為5+2(即n)，然后將11355按照大小插入到序列1234567中，得到111233455567然后將兩個序列排在一起 31551111233455567 31551111233455567

16、 15511113455567 55111455567 51115567 11157 17第一步推導(dǎo)：將上下兩個序列同時去掉上行序列的第一個元素3(用黃色表示)，去掉下行序列的第一個無重復(fù)的元素2(用紅色表示)。生成一條邊()。由上序列確定3（黃色），再確定2（紅色），在下序列最小無重元，于是生成邊23。（并消除紅黃色點。）依此類推，減到下面剩最后兩個元素，這兩個元素形成最后一條邊。最后形成樹。 （生成邊的序列23，13，45，56，15，17） 上述算法描述：給定序列b=(b1b2bn-2) ，設(shè)a=(123n-1 n)將b的各位插入a，得a，對( )做操作。a是2n-2個元的可重非減序列。

17、ba操作是從a中去掉最小無重元，設(shè)為a1,再從b和a中各去掉一個b中的第一個元素，設(shè)為b1，則無序?qū)?a1,b1)是一條邊。重復(fù)這一操作，得n-2條邊，最后a中還剩一條邊，共 n-1條邊，正好構(gòu)成一個樹。b中每去掉一個元，a中去掉2個元。 由算法知由樹T得b=(b1b2bn-2) ， 反之，由b可得T。 即 f：Tb 是一一對應(yīng)。 由序列確定的長邊過程是不會形成回路的。ba因任意長出的邊 (u , v) 若屬于某回路，此回路中必有一條最早生成的邊，不妨就設(shè)為 (u , v) ，必須使u，v都在長出的邊中重復(fù)出現(xiàn)，但照算法u，v之一從下行消失，不妨設(shè)為u，從而不可能再生成與u有關(guān)的邊了，故由(

18、)得到的邊必構(gòu)成一個n個頂點的樹。 證：由一棵n個頂點的樹可得到一個長度為n2的序列，且不同的樹對應(yīng)的序列 不同*，因此 。 *對n用歸納法可證。 反之，由一個長度為n2的序列(每個元素為1 n 的一個整數(shù))，可得到一棵樹，且不同的序列對應(yīng)的樹是不同的，因此 22nnnTnT2nnT1.1.3 3 排列與組合排列與組合當(dāng)r=n時稱為全排列。一般不說可重即無重?？芍嘏帕械南鄳?yīng)記號為 。),(rnP定義定義 從n個不同的元素中，取r個不重復(fù)的元素，按次序排列，稱為從n個中取r個的無重?zé)o重排列排列。 nrP排列的個數(shù)用P(n,r)或 表示。),(rnC對應(yīng)于可重組合有記號 。定義定義 從n個不同元素

19、中取r個不重復(fù)的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合無重組合。rn組合的個數(shù)用C(n,r)或 表示。從n個中取r個的排列的典型例子是從n個不同的球中，取出r個，放入r個不同的盒子里,每盒1個。第1個盒子有n種選擇，第2個有n-1種選擇，第r個有n-r+1種選擇。故有 P(n,r)=n(n-1)(n-r+1)有時也用nr記 P(n,r)=n(n-1)(n-r+1)=n!/(n-r)!（1）從n個中取r個的無重排列 P(n,r)=n(n-1)(n-r+1)例：n=3, r=2AB, BA, CA,AC, BC, CB。（2）從n個中取r個的可重排列rnrnP),(例

20、：n=3, r=2AB, BA, CA,AC, BC, CB,AA, BB, CC。若球不同，盒子相同，則是從n個中取r個的組合的模型。若放入盒子后再將盒子標(biāo)號區(qū)別，則又回到排列模型。每一個組合可有r!個標(biāo)號方案。故有 C(n,r)r!=P(n,r),如:n=3,r=2,P(n,r)=3!/1!=6, AB,BA,AC,CA,BC,CBC(n,r)=3!/(1!2!)=3, AB, AC, BC)!( !rnrnrnC(n,r)=P(n,r)/r!=nr/r!=（1）從n個中取r個的無重組合無重組合 )!( !),(rnrnrnrnC（2）從n個中取r個的可重組合(以后介紹)。例：n=3, r

21、=2AB, BC, CA,AA, BB, CC例：n=3, r=2AB, BC, CA, 要點：相同元素的排列 例：求3個1，2個2的全排列數(shù)，n=5, 得到 11122, 11212, 12112, 21112, 11221, 12121, 21121, 12211, 21211, 22111 10! 2! 3! 5)2 , 3; 5(P 求r1個1，r2個2，rt個t的排列數(shù)。 設(shè)r1+r2+rt=n, 設(shè)此排列數(shù)為P(n; r1,r2,rt), 對1，2，t分別加下標(biāo)，得到 P(n；r1,r2,rt)r1!r2!rt! = n!tttrrrnrrrnrrrnP212121!),;(解：解

22、：RRYY, RYRY, RYYR, YYRR, YRYR, YRRY。例例1-201-20 紅，黃二色的旗各兩面，4面排成一排，有多少種方案？6) ! 2(! 42YYRR, 代表代表Y1 Y2 R1 R2, Y1 Y2 R2 R1, Y2 Y1 R1 R2，Y2 Y1 R2 R1。例例1-131-13 5面不同的旗幟，面不同的旗幟，20盆不同的花，兩盆不同的花，兩端是不同的旗幟，中間放端是不同的旗幟，中間放3盆不同的花。有多盆不同的花。有多少方案？少方案？解：解：5面旗取面旗取2面排列面排列 P(5,2)=54=20，20盆花取盆花取3盆排列盆排列 P(20,3)=201918=6840，

23、由乘法法則，由乘法法則， 206840136800。例例1-121-12 男生7名，女生3名，排成一列，頭和尾為男生，女生不相鄰。有多少方案？解解1 男生全排列（男生全排列（7！種），！種）， 男男男男男男男男男男男男男男女生插入女生插入6個間隔，依次有個間隔，依次有6，5，4個選擇個選擇 （相當(dāng)于（相當(dāng)于6個間隔取個間隔取3個，排列）個，排列）456! 7) 3 , 6(! 7P456! 7! 3) 3 , 4()4 , 7(! 3CP總計總計解解2 女生全排列，女生全排列，3！種，！種， 7男生取男生取4人插入人插入4個位置，個位置，P(7,4)種。種。 男男女男女男女男女男女男女男 4個

24、個位置，可重取位置，可重取3個，個，C(4,3)種。種。 3個可重位置排序，個可重位置排序，3！種。！種。由由1-6節(jié)節(jié)) ! 3 ! 3/(! 6) 3 , 134() 3 , 4( CC解解3 注意注意1：男男女女男男女女男男女女男男 4個個位置，可重取位置，可重取3 3個，則多個男相鄰。個，則多個男相鄰。設(shè)無重取設(shè)無重取3 3個，則個，則至多至多2 2個男相鄰。個男相鄰。 注意注意2：只能考慮只能考慮4個個位置。位置。設(shè)設(shè)5個個位置位置 男男女男女男女男女男女男女男則由則由 男男11女女, , 得到得到 男男1 1男男2 2女女,且由且由 男男22女女, , 得到得到 男男1 1男男2

25、2女女, , 重復(fù)重復(fù)(2)當(dāng)當(dāng) 取取3， 有有5種選擇，種選擇， 從其余從其余8個數(shù)字取個數(shù)字取2個排列。個排列。12nn3n0n728280448280)2 , 8(51P例例1-15 2000到5000間的偶數(shù)中，由不同數(shù)字組成的4位數(shù)的數(shù)目。0123nnnn3n0n解解1 設(shè)該設(shè)該4位數(shù)為位數(shù)為取取0,2,4,6,8； 取取2,3,4（為何分組）（為何分組）3n0n12nn448)2 , 8(42P 從其余從其余8個數(shù)字取個數(shù)字取2個排列。個排列。 (1)當(dāng)當(dāng) 取取2,4, 有有4種選擇，種選擇，12nn例例1-15 (為了顯示二解之差，修改了數(shù)據(jù)為了顯示二解之差，修改了數(shù)據(jù)) (注意

26、:為何后考慮為何后考慮 )0123nnnn3n0n12nn3n3n0n0n12nn224)2 , 8(22P728504224504)2 , 8(33P解解2 設(shè)該設(shè)該4位數(shù)為位數(shù)為 取取0,2,4,6,8 取取2,3,4（為何分組）（為何分組） (1)當(dāng)當(dāng) 取取2,4, 有有2種選擇，種選擇， 從其余從其余8個數(shù)字取個數(shù)字取2個排列。個排列。 (2)當(dāng)當(dāng) 取取0,6,8， 有有3種選擇，種選擇， 從其余從其余8個數(shù)字取個數(shù)字取2個排列。個排列。例例1-15 解解3 取取0,2,4,6,8 取取2,3,4(1)當(dāng)當(dāng) 取取2,4, 取取2,3,4(有有2種種)， 有有1種種, 有有7種種. 共共

27、227=28(2)當(dāng)當(dāng) 取取2,4, 取非取非2,3,4(有有7種種)， 有有2種種, 有有7種種. 共共2727=196(3)當(dāng)當(dāng) 取取0,6,8, 取取2,3,4(有有3種種)， 有有2種種, 有有7種種. 共共3327=126(4)當(dāng)當(dāng) 取取0,6,8, 取非取非2,3,4(有有6種種)， 有有3種種, 有有7種種. 共共3637=3783n0n3n3n0n0n728378126196282n1n0n0n1n1n1n3n3n2n2n2n例例1-16 5個女生和7個男生選出5人，不允許男生甲和女生乙同時選中。有多少方案？1201238910) 3 ,10(7921234589101112)

28、5 ,12(CC解解1 12人取5人的組合 甲和乙同時參加的組合 合計：792120672 25212345678910)5 ,10(4201234789102)4 ,10(2CC例例1-16 解解2 甲或乙之一參加的組合 甲和乙同時不參加的組合 合計：420252672例例1-18 英文Wellcome中， 3個母音e,o,e中e重復(fù)， 5個子音w,l,c,m中l(wèi)重復(fù)。 8個字母全排列，3個母音不相鄰， 多少排列？00000解：解：5個子音排列，5!/2=60。 3個母音插入6個位置，654/260例例1-19 從1,300中取3個不同的數(shù)，使這3個數(shù)的和能被3整除，有多少種方案？14851

29、001000000485100100) 3 ,100(33C解：解： 將1,300分成3類： （為何分類）（為何分類） A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要滿足條件，有四種解法：（為何分類）（為何分類） 1)3個數(shù)同屬于A; 2)3個數(shù)同屬于B 3)3個數(shù)同屬于C; 4)A,B,C各取一數(shù).故共有例例1-20 用11, 12, 13的方塊鋪設(shè)17的模塊，有多少方案？解：用7塊11，1種 用5塊11，1塊12，6!/5!=6 種 用4塊11，1塊13，5!/4!=5 種 用3塊11

30、，2塊22，5!/(3!2!)=10 種 用2塊11，1塊12，1塊13，4!/2!=12 種 用1塊11，3塊12，4!/3!=4種 用1塊11，2塊13，3!/2!=3種 用2塊12，1塊13，3!/2!=3 種合計：165101243344種例例1-211-21 8人分4組，每組2人，有多少方案？解解1 某人選同組7個選擇， 余6人之一選同組5個選擇， 余4人之一選同組3個選擇， 合計105357 1052484！解解2 8人全排列，8！個選擇，按排列分組 1,2,3,4,5,6,7,8， 同組交換，重復(fù)度2222， 4組排列，重復(fù)度4！， 合計105)2(4! 8! 41! 2! 2!

31、 4! 2! 4! 6! 2! 6! 84！解解3 8人選第一組，C(8,2)個選擇， 余6人選第二組，C(6,2)個選擇， 余4人選第三組，C(4,2)個選擇， 4組排列，重復(fù)度4！， 合計例例1-22 某車站有某車站有6個入口處，每個入口處每次個入口處，每個入口處每次只能進(jìn)一人，一組只能進(jìn)一人，一組9個人進(jìn)站的方案有多少？個人進(jìn)站的方案有多少？解：解：一進(jìn)站方案表示成：00011001010100其中“0”表示人，“1”表示門框，其中“0”是不同元，“1”是相同元。給n-1個“1”n個門只用n-1個門框。 任意進(jìn)站方案可表示成上面14個元素的一個排列。abc 1 1 de 1 f 1 g

32、1 hi注意：注意：門框確定門的排序，門框不必排序門框確定門的排序，門框不必排序解解1 1 標(biāo)號可產(chǎn)生5!個14個元的全排列。故若設(shè)x為所求方案，則 x5!=14! x=14!/5!=726485760解解2 2 在14個元的排列中先確定“1”的位置，有C(14,5)種選擇，再確定人的位置，有9！種選擇。故C(14,5)9!即所求。解解3 3 把全部選擇分解成若干步，使每步宜于計算。不妨設(shè)9個人編成1至9號。1號有6種選擇；2號除可有1號的所有選擇外，還可（也必須）選擇當(dāng)與1號同一門時在1號的前面還是后面，故2號有7種選擇；3號的選擇方法同2號，故共有8種。以此類推，9號有14種選擇。故所求方

33、案數(shù)為67891011121314 解解4 4 9個人全排列有9！種。10個空位（兩端和8個間隔）插入5個門框，每個空位可以有多個門框。這是從10個不同元中，可重復(fù)取5個的組合， （1.6節(jié)給出公式）總計： ! 5!14)5 ,10(! 9! 9! 5!14)5 , 1510()5 ,10()5 ,10(CCCC如2個人，3個門。34個方案。12MM, 21MM, 1M2M, 2M1M, M12M, M21M, M1M2, M2M1, 1MM2, 2MM1, MM12, MM21,1.1.4 4 圓周排列圓周排列 要點：要點：從n個中取r個的圓排列的排列數(shù)為 P(n,r)/r , 2rn 以4

34、個元素為例：下列4個為同一個圓排列 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123如：P(4,4)/4=61234, 1243, 1324, 1342, 1423, 1432例例1-241-24 5 5個男生和個男生和3 3個女生圍圓桌坐，個女生圍圓桌坐，(1)A,B(1)A,B不相鄰有多少方案？不相鄰有多少方案？(2)3(2)3女生不相鄰，有多少？女生不相鄰，有多少？解：解：(1)B(1)B以外以外7 7人圓周排列人圓周排列6 6！種，！種，B B插入插入5 5個間隔個間隔( (除去除去A A兩邊兩邊2 2個間隔個間隔) )?？傆??？傆? 6！

35、5 5個方案。個方案。(2)5(2)5男生圓排列男生圓排列4 4！種，！種，3 3女生依次插入女生依次插入5 5個間個間隔?？傆嫺??？傆? 4！5 54 43 3個方案。個方案。 例例1-251-25 n n對夫妻圍一圓桌而坐，每對夫妻相對夫妻圍一圓桌而坐，每對夫妻相鄰而坐，有多少方案？鄰而坐，有多少方案？解： .)()()()(162)!13(2)!1(32)!1(3311221122332233112211331133223322113311221122332233112211331133223322113fmmffmmffmfmfmfmmffmmffmmffmfmfmfmmffmfmfm

36、fmfmfmfmfmfmfmfmfmfmfmfmfmfmfmnnnnn時， 要點：要點：從n個中取r個的項鏈排列項鏈排列的排列數(shù)為 P(n,r)/2r, 3rn 項鏈排列項鏈排列就是說排列的方法和項鏈一樣,在圓排列的基礎(chǔ)上，正面向上和反面向上兩種方式放置各個數(shù)是同一個排列。 例例 下面兩種方式實際上表示的都是3個元素的同一種項鏈排列。 P(3,3)/(23)=1 123, 231, 312, 321, 213, 132 1 1 2 3 3 21.5 全排列的生成算法全排列的生成算法全排列的生成算法就是對于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。介紹全排列生成的主要算

37、法：(A) 序數(shù)法(B) 字典序法(C) 鄰位對換法1.5.1序數(shù)法, 110, 200, 32023013! 11! 20! 32201! 11! 22! 331! 499990105101100108801510910910910911015092120202110012121212112123012301234012301234aaa如新進(jìn)制如十進(jìn)制如二進(jìn)制1! 41! 3! 331! 2! 22! 3311! 11! 22! 33! 11! 22! 33! 11! 22! 331! 4證明：新進(jìn)制由序數(shù)2，0，1 ，求十進(jìn)制m13 23！02！11！13) 1 , 0 , 2(),(2

38、, 0424340,! 3! 32363231,! 2! 2! 2! 36213212),(! 1! 2! 3131123323123123123aaaannaannaaannaaaaaan序數(shù)余數(shù)余數(shù)余數(shù)序數(shù)由十進(jìn)制m13，求序數(shù)2，0，1 1, 2 , 1,0! 1! 2)!2()!1(1221niiaaananaminn其中序數(shù) n!個，對應(yīng)n元的n!個序列。規(guī)則(序列序數(shù))：序列(p)= 是(p)中數(shù)字i+1后面比i+1小的數(shù)的個數(shù) 如 (p)=(4213) 對應(yīng) =(301) n4 (p)=(3412) 對應(yīng) =(220)規(guī)則(序數(shù)序列)：如其中的序列(220)所對應(yīng)的排列: 先由

39、=2決定4的位置 x4xx 再由 =2決定3的位置 34xx 再由 =0決定2的位置 34x2 則 3412),(21nppp),(121aaan),(123aaa),(123aaa1aia3a2a 對給定的字符集中的字符規(guī)定了一個先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個全排列的先后是從左到右逐個比較對應(yīng)的字符的先后。1.5.2 字典序法 例例 字符集1,2,3,較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。一個全排列可看做一個字符串，字符串可有前綴前綴、后綴后綴。 對給定的字符集中的字符規(guī)定了一個先先后關(guān)系后關(guān)系，在此基礎(chǔ)上規(guī)定兩個全排列的先后是從左到右逐個

40、比較左到右逐個比較對應(yīng)的字符的先后。3544 3135生成給定全排列的下一個排列：所謂一個的下一個一個的下一個就是這一個這一個與下一個下一個之間沒有其他沒有其他的的。這就要求這一個與下一個有盡可能長長的共同前綴共同前綴，也即變化限制在盡可能短短的后綴后綴上。例例 求83964 47521的下一個排列。找出比右邊數(shù)字小的第一個數(shù)4在后綴7521中找出比4大的最小數(shù) 54，5 對換成為 839657421將此后綴7421翻轉(zhuǎn)成為 1247接上前綴83965得到839651247即839647521的下一個。1.5.3 鄰位對換法 遞減進(jìn)位制數(shù)法的中介數(shù)進(jìn)位不頻繁，求下一個排列在不進(jìn)位的情況下很容易

41、。這就啟發(fā)我們，能不能設(shè)計一種算法，下一個排列總是上一個排列某相鄰兩位對換得到的。遞減進(jìn)位制數(shù)字的換位是單向單向的，從右向左，而鄰位對換法的換位是雙向雙向的?；顒訑?shù)是箭頭所指相鄰數(shù)比自己小的數(shù)。對換規(guī)則：活動數(shù)中最大的數(shù)m，交換箭頭所指相鄰數(shù)。同時，比m大的數(shù)，改變方向。42312431234123143214324134214321mmmmmmmm1.6 允許重復(fù)的組合與不相鄰的組合1.6.1 允許重復(fù)的組合從n個不同元素中取r個可重復(fù)的元素的可重組合數(shù)目 C(n,r) = C( n+r-1,r)如n=3，r=2。C( 3+2-1,2)= C( 4,2)=6 AA, BB, CC, AB,

42、AC, BC相當(dāng)于r個相同的球放入n個互異的盒子 200，020，002，110，101，011 r個相同的球 / 001001100 / /n-1個相同的盒壁),(rnC 的計數(shù)問題相當(dāng)于r相同的球放入n個互異的盒子，每盒球的數(shù)目不同的方案的計數(shù)。而后一問題又可轉(zhuǎn)換為r個相同的球與n-1個相同的盒壁的排列的問題。) 1,(), 1(),(), 1()!1( !)!1(rnCrnCrnCrrnCnrrn所求計數(shù)為不含“” 至少含一個“”), 1(),(), 1(),(), 1(),(), 1(1,.,111, 2 , 1, 1:1),(,.,11212121212121rrnCrnCrrnCr

43、nCfrrnCrnCfrrnCbbbrrnrnbbbriiabbbbaaafnaaarnCaaarnrriirrrr則是單射，是單射，個中無重取從則滿足使得是無重組合，構(gòu)造函數(shù)個中可重取從證：234,134,124,123,4222,122,112,111,44) 1 , 4(), 1(134,314,.,1144311422, 312, 101134122:22211122,32 , 1321321為個為個個中無重取從則滿足其中：是無重組合，構(gòu)造函數(shù)個中可重取從如：bbbaaaCrrnCrnrnfnrn4)(zyx例1-29 有多少項？yzxzxyzyzxyxyxzxzyyzxyzzxyxz

44、yxzyxC3333332222222224444444444121212666)(15) ! 2! 4/(! 6)4 , 134(解：解：從3個元素可重復(fù)的取4個的組合數(shù)目。從n個不同元素中取r個的可重排列數(shù)目 aa,bb,cc,ab,ac,bc,ba,ca,cb9)2 , 3(, 2, 3),(6)2 , 3(, 2, 3)!/(!),(PrnnrnPPrnrnnrnPr如如總結(jié)：總結(jié)：從n個不同元素中取r個不重排列數(shù)目 ab,ac,bc,ba,ca,cb6)2 , 4()2 , 3(, 2, 3), 1(),(3)2 , 3(, 2, 3)!( !/!),(CCrnrrnCrnCCrnr

45、nrnrnC如如總結(jié)：從n個不同元素中取r個不重組合數(shù)目 ab,ac,bc從n個不同元素中取r個的可重組合數(shù)目 aa,bb,cc,ab,ac,bc1.6.2 不相鄰的組合 從n個不同元素中取r個不相鄰的元素的不相鄰組合數(shù)目C( n-r+1,r) 如n=5,r=2. C( 5-2+1,2)= C( 4,2)=6 AC, AD, AE, BD, BE, CE), 1(111, 1,1212122112121rrnCbbbrnbbbrabababnaaaaaarrrrrr則滿足令屬于不相鄰的組合設(shè)證明：)3 , 3()3 , 135(1353332132521315312)3 , 7()3 , 13

46、5(13573765432172561515511354321CCCC）個組合（取，對應(yīng)從，改為，）不相鄰：（）個組合（取，對應(yīng)從，改為，）可重合：（個組合，取，從說明：1.6.3 線性方程的整數(shù)解的個數(shù)問題已知線性方程 和 都是整數(shù) ， 求此方程的非負(fù)整數(shù)解的個數(shù)。nbxxxn,21b1n證：方程的每個非負(fù)整數(shù)解 對應(yīng)一個將b個無區(qū)別的球，放進(jìn)n個有標(biāo)志的盒子 的情況，允許一盒多于一個球的，故非負(fù)整數(shù)解的數(shù)目等價于1到n 正整數(shù)取b個作允許重復(fù)的組合，其組合數(shù)為),(21n),(21nxxxbbn1。bn21ni, 2 , 1,2211nnxxx使等價于 盒有 個球， 。ixi321nxxx

47、10353133例如，0120030212011113000302101201021.6.4 組合的生成 設(shè)1,2,3,4,5,6中取3個的組合，20個， 按照字典序排列。 123，124，125，126，134， 135，136，145，146，156， 234，235，236，245，246， 256，345，346，356，456。 第1位1到4，第2位2到5，第3位3到6。 如256，345，346，356，456。 256中，5和6到最大。 2加1為3，后接4，5等。為345。 如156，234，235，236，245， 156中，5和6到最大。 1加1為2，后接3，4等。為234。

48、 236中，6到最大。 3加1為4，后接5等。為245。1.7 組合意義的解釋例例1-30 簡單格路問題從 (0,0)點出發(fā)沿x軸或y軸的正方向每步走一個單位，最終走到(m,n)點，有多少條路徑？y (m,n).0 . . . xmnmnm),()0 , 0( 無論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個x表示x方向上的一步，一個字母y表示y方向上的一步。 則(0,0)(m,n)的每一條路徑可表示為m 個x與n個y的一個相同元素排列。將每一個相同元素排列的x與y分別編號，可得m!n!個m+n元的無重全排列。,!)!(1232121321yyxxxyyxxxnmnmmnm

49、(c,d)(a,b)acbdacdcbadcbabdacmnmnmnmnmnmPnmnmnmnmPnmnmP)()(),)(,(),(),(,!)!(),;()!(!),;(),;(的簡單格路數(shù)為到則由設(shè)故則設(shè)所求方案數(shù)為 xxxyy, xxyxy, xyxxy, yxxxy, xxyyx, xyxyx, yxxyx, xyyxx, yxyxx, yyxxx 10! 2! 3)!23()2 , 3; 23(),;(, 2, 3PnmnmPnm則設(shè) 例例1-44 在上例的基礎(chǔ)上若設(shè)mn，求(0,1)點到(m,n)點不接觸對角線x=y(xy)的格路的數(shù)目 (“接觸”包括“穿過”) 從(0,1)點到

50、(m,n)點的格路，有的接觸x=y，有的不接觸。 對每一條接觸x=y的格路，做(0,1)點到第一個接觸點部分關(guān)于x=y的對稱格路，這樣得到一條從(1,0)到(m,n)的格路。 容易看出從(0,1)到(m,n)接觸x=y的格路與 (1,0)到(m,n)的格路(必穿過x=y)一一對應(yīng)y y=x (m,n)0 (1,0) x(0,1). .y x-y=1 (m,n) x(0,0) (1,-1). . .mnmnmnmnmnmmnnmnmnmmnmmnm111)!1( !)!1()!1( !)!1()!1( !)!1(111故所求格路數(shù)為(0,1)到(m,n)路徑數(shù)減去(1,0)到(m,n)路徑數(shù)。2

51、2431213232111mnmnm如m=2,n=3. 方案數(shù)2。yyyxx, yyxyx 例 若條件改為可接觸但不可穿過，則限制線要向下或向右移一格，得xy=1， (0,0)關(guān)于xy=1的對稱點為(1,-1). 所求格路數(shù)為(0,0)到(m,n)路徑數(shù)減去(1,-1)到(m,n)路徑數(shù)如m=2,n=3. 方案數(shù)5。yyyxx, yyxyx, yxyxy, yxyyx, yyxxymnmnmnmnnmnmnmmnmmnm11)!1()!1()!(!)!(1 組合意義或組合證明，含意強(qiáng)弱的不同。承認(rèn)組合證明與其他證明有相同的“合法性”。等式1.例1-31 組合意義：從1,n去掉一個r子集，剩下一

52、個(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個一一對應(yīng)。故又證：),()!(!),(),(),(),(),(rnnCrnrnrnCrnnCrnCrnnCrnC 等式2.例1-32 組合意義： ) 1, 1(), 1(),(), 1(1) 1, 1(1,1, 1 ) 1, 1(), 1(),(112121rnCrnCrnCrnCarnCanaaaaaanrnCrnCrnCrr共有種方案有種方案有對取法分類：設(shè)，取從 另一個組合意義 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) 另可證),(

53、)!(!)()!(!)!1()!()!1()!1()!1(!)!1() 1, 1(), 1(rnCrnrnrrnrnrnrnrnrnrnrnCrnC 楊輝三角除了(0,0)點，都滿足此遞推式 C(3,2)=3, C(2,2)+C(2,1)=1+2=3 C(4,1)=4, C(3,1)+C(3,0)=3+1=4 等式3 例1-33rrnrrnnn1110rrnnnrrnrrnrrnrrnrrnrrn110112111證：證：可從例1-32推論，也可做一下組合證明 組合意義： 從1,n+r+1取r個的組合是右邊。 左邊最后一項不含1 ，n+r個取r 左邊最后第二項含1不含2, n+r-1個取r-1 左邊最后第三項含1,2不含3, n+r-2個取r-2 , 左邊第一項含1,2,r, 則不取r+1以后rrnrrnnn1110 另組合意義:從(0,0)到(n+1,r),過且僅過一條帶箭頭的邊,而過這些邊的路徑有(從下到上) 故