講義參考教案1

1、1 Combinatorics馬昱春 第一章排列組合2第一章排列組合1.1 加法法則與乘法法則分類計數(shù)和分步計數(shù)從甲地到乙地，可以乘火車，也可以乘汽車，一天中，火車有3班，汽車有2班那么一天中，乘坐這些交通工具從甲地到乙地共有多少種不同的走法？解答： 325 種不同的走法從甲地到乙地，要從甲地選乘火車到丙地，再于次日從丙地乘汽車到乙地一天中，火車有3班，汽車有2班那么兩天中，從甲地到乙地共有多少種不同的走法？解答：共有 326 種不同的走法31.1 加法法則與乘法法則 加法法則 The Sum Rule設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。集合論語言

2、：若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。 例 某班選修企業(yè)管理的有 18 人，不選的有 10 人，則該班共有 18 + 10 = 28 人。41.1 加法法則與乘法法則 乘法法則 The Product Rule 設(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 。例 某種字符串由兩個字符組成，第一個字符可選自a，b，c，d，e，第二個字符可選自1，2，3，則這種字符串共有5 3 = 1

3、5 個。51.1 加法法則與乘法法則例 某種樣式的運動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案。若此例改成底色和條紋都用紅、藍、橙、黃四種顏色的話，則，方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。在乘法法則中要注意事件 A 和 事件 B 的相互獨立性。61.1 加法法則與乘法法則例 1)求小于10000的含1的正整數(shù)的個數(shù) 2)求小于10000的含0的正整數(shù)的個數(shù)1)小于10000的不含1的正整數(shù)可看做4位數(shù),但0000除外. 故有999916560個. 含1的有：99996560=3439個另: 全部4位數(shù)有

4、104 個,不含1的四位數(shù)有94 個, 含1的4位數(shù)為兩個的差: 104 94 = 3439個72)求小于10000的含0的正整數(shù)的個數(shù)“含0”和“含1”是否可以直接套用？0019含1但不含0。 在組合的習(xí)題中有許多類似的隱含的規(guī)定，要特別留神。 不含0的1位數(shù)有9個，2位數(shù)有92個，3位數(shù)有93個，4位數(shù)有94個 不含0小于10000的正整數(shù)有 9 + 92 + 93 + 94 =(951)/(91)=7380個含0小于10000的正整數(shù)有 99997380=2619個81.2排列與組合定義 排列 Permutation從n個不同的元素中，取r個不重復(fù)的元素，按次序排列，稱為從n個中取r個的

5、無重排列。排列的個數(shù)用P(n,r)表示，或者 。當(dāng)r=n時稱為全排列。一般不說可重即無重。定義 組合 Combination從n個不同元素中取r個不重復(fù)的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合。組合的個數(shù)用C(n,r)表示或者91.2排列與組合從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記n(n-1)(n-r+1)全排列：P(n,n) = n!遞推關(guān)系：P(n,r) = nP(n-1,

6、r-1) =P(n-1,r) + rP(n-1,r-1)101.2排列與組合若球不同，盒子相同，則是從n個中取r個的組合的模型。若放入盒子后再將盒子標號區(qū)別，則又回到排列模型。每一個組合可有r!個標號方案。故有 C(n,r)r!=P(n,r)=C(n,r)=P(n,r)/r!=nr/r!= =11排列組合問題的來源排列組合問題，最早見于我國的易經(jīng)一書所謂“四象”就是每次取兩個爻(yo )的排列，“八卦”是每次取三個爻的排列在漢代數(shù)學(xué)家徐岳的數(shù)術(shù)記遺（公元2世紀）中，也曾記載有與占卜有關(guān)的“八卦算”，即把卦按不同的方法在八個方位中排列起來它與“八個人圍一張圓桌而坐，問有多少種不同坐法”這一典型的

7、排列問題類似11世紀時，邵雍還進一步研究了六十四卦的排列問題唐朝僧人一行曾經(jīng)研究過圍棋布局的總數(shù)問題古代的棋盤共有17路，289個點，后來發(fā)展到19路361個點一行曾計算過一切可能擺出的棋局總數(shù)17世紀，北宋時期沈括在夢溪筆談中，進一步討論了圍棋布局總數(shù)問題他利用一些排列、組合的辦法對一行的計算作了分析沈括指出，當(dāng)361個棋子全用上時，棋局總數(shù)達到1000052 的數(shù)量級121.2排列與組合例 有5本不同的日文書，7本不同的英文書，10本不同的中文書。1)取2本不同文字的書； 57+510+710=155;2)取2本相同文字的書；C(5,2)+C(7,2)+C(10,2) =10+21+45=

8、76;3)任取兩本書 155+76=231= C(5+7+10,2)131.2排列與組合多重排列：2個a, 3個b，4個c，其多重排列記為加上下標以區(qū)別 a1a2b1b2b3c1c2c3c4a下標排列有2!，b下標排列有3!，c下標排列有4！141.2排列與組合求r1個1，r2個2，rt個t的排列數(shù)，設(shè)r1+r2+rt=n,設(shè)此排列數(shù)為P(n;r1,r2,rt)對1，2，t分別加下標，得到P(n;r1,r2,rt)r1!r2!rt! = n! P(n;r1,r2,rt) = 多項式展開=151.2排列與組合圓排列：從n個中取r個的圓排列的排列數(shù)為 P(n,r)/r , 2rn以4個元素為例 1

9、2 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123161.2排列與組合項鏈排列：排列的方法和項鏈一樣,在圓排列的基礎(chǔ)上，正面向上和反面向上兩種方式放置各個數(shù)是同一個排列。例 下面兩種方式實際上表示的都是3個元素的同一種排列。從n個中取r個的項鏈排列的排列數(shù)為P(n,r)/2r, 3rn 1 1 2 3 3 2171.2排列與組合例 從1,300中取3個不同的數(shù)，使這3個數(shù)的和能被3整除，有多少種方案？解 將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)

10、=3,6,9,300. 要滿足條件，有四種可能： 1)3個數(shù)同屬于A; 2)3個數(shù)同屬于B 3)3個數(shù)同屬于C; 4)A,B,C各取一數(shù).故共有3C(100,3) =485100 =1485100181.2排列與組合例 某車站有6個入口處，每個入口處每次只能進一人，一組9個人進站的方案有多少？解一進站方案表示成：XX11 XX 1X1X1XXX其中“X”表示某人，“1”表示門框，其中“X”是不同元，“1”是相同元。任意進站方案可表示成上面14個元素的一個排列。271459836191.2排列與組合XX11 XX 1X1X1XXX解法1給每個方案的門標號可產(chǎn)生5!個14個元的全排列。故若設(shè)x為所

11、求方案數(shù)，則 x5!=14! x=14!/5!=726485760解法2在14個元的排列中先確定“1”的位置，有C(14,5)種選擇，再確定人的位置，有9！種選擇。故C(14,5)9!即所求201.2排列與組合解法3把全部選擇分解成若干步，使每步宜于計算。不妨設(shè)9個人編成1至9號。1號有6種選擇；2號除可有1號的所有選擇外，還可（也必須）選擇當(dāng)與1號同一門時在1號的前面還是后面，故2號有7種選擇；3號的選擇方法同2號，故共有8種。以此類推，9號有14種選擇。故所求方案為 6*7*8*.*14 =14!/5!=72648576013221內(nèi)容回顧加法法則和乘法法則排列從n個不同的球中,取出r個,

12、放入r個不同的盒子里,每盒1個。P(n,r)=n(n-1)(n-r+1) = 組合從n個不同的球中,取出r個,放入r個相同的盒子里,每盒1個C(n,r)=P(n,r)/r!=221.3 模型轉(zhuǎn)換“一一對應(yīng)”概念是一個在計數(shù)中極為基本的概念如我們說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)。231.3 模型轉(zhuǎn)換例 在100名選手之間進行淘汰賽(即一場的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問要舉行幾場比賽？解 一種常見的思路是

13、按輪計場，費事。淘汰的選手與比賽(按場計)集一一對應(yīng)。模型轉(zhuǎn)換：99場比賽。24格路問題從 (0,0)點出發(fā)沿x軸或y軸的正方向每步走一個單位，最終走到(m,n)點，有多少條路徑？(0,0)(m,n)的每一條路徑可表示為m 個x與n個y的一個有重排列。將每一個有重排列的x與y分別編號，可得m!n!個m+n元的無重全排列。C(m+n,m)設(shè)ca,db,則由(a,b)到(c,d)的簡單格路數(shù)為y (m,n).0 . . . xxyxxxyy (c,d)(a,b)251.3 模型轉(zhuǎn)換例 在上例的基礎(chǔ)上若設(shè)mn，求(0,1)點到(m,n)點不接觸對角線x=y的格路的數(shù)目 (“接觸”包括“穿過”)(0,

14、1)(m,n)y=x(1,0)從(0,1)點到(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)261.3 模型轉(zhuǎn)換故所求格路數(shù)為y y=x (m,n)0 (1,0) x(0,1). .271.3 模型轉(zhuǎn)換求(0,0)點到(m,n)點可接觸但不可穿過對角線x=y的格路的數(shù)目;限制線要向下或向右移一格，得xy=1;問題轉(zhuǎn)化為求(0,1)到(m,n)不接觸x-y=1的格

15、路數(shù)。(0,0)關(guān)于xy=1的對稱點為(1,-1).利用上一問的方法所求格路數(shù)為 (m,n)y=x(1,-1)x-y=1(0,0)28281.3 模型轉(zhuǎn)換例 (Cayley定理) n個有標號的頂點的樹的數(shù)目等于nn-2。用n-1條邊將1,2,3n點連接起來的連通圖的數(shù)目nn-2。生成樹的Cayley計數(shù)公式nn-2是英國數(shù)學(xué)家Cayley于1889年給出。1231231232929Cayley, 凱萊, 英國數(shù)學(xué)家, (1821-1895)發(fā)表900多篇論文。Cayley1838年進入劍橋大學(xué)三一學(xué)院學(xué)習(xí)，1842年畢業(yè)后在劍橋大學(xué)教書四年后來從事律師14年，在從事律師的14年間寫了200多篇

16、數(shù)學(xué)文章，1863年Cayley被聘為劍橋大學(xué)教授，又得以繼續(xù)從事數(shù)學(xué)工作。他在生前得到了他所處時代一位科學(xué)家可能得到的幾乎所有重要榮譽 關(guān)于Cayley定理的nn-2計數(shù)公式，加拿大艾爾伯達大學(xué)教授JohnWMoon在1967年專門寫了一篇文章，給出這個定理的十種不同證明，此后此定理又出現(xiàn)了更多的證法。30301.3 模型轉(zhuǎn)換 | | 41 2 5 31. 刪葉子：逐個摘去標號最小的葉子2. 序列中記錄？葉子？生長點？葉子的相鄰頂點(不是葉子，是內(nèi)點)形成一個序列，序列的長度為n-2給定一棵有標號的樹,通過逐步刪除葉子，是否能夠得到某種序列，可以表示樹的結(jié)構(gòu)呢？邊上的標號表示摘去葉的順序。(摘去一個葉子相應(yīng)去掉一條邊)3131以此類推，得到序列31551,長度為72 = 5這是由樹形成序列的過程。 | | 41 2 5 3 | | | | | | | | 3 3 1 3 1 5 3 1 5 5 3 1 5 5 1 32321.3 模型轉(zhuǎn)換由序列形成樹的過程：當(dāng)前序列對應(yīng)的可以刪掉的葉子必然不在該序列中；且最小的那個葉子被刪掉了，所以被刪掉的邊是(23)然后將兩個序列排在一起 3155112345673 1 5 5 1可能的被