排列組合公式演示文稿當(dāng)前第1頁\共有121頁\編于星期二\7點(diǎn)排列組合公式ppt課件當(dāng)前第2頁\共有121頁\編于星期二\7點(diǎn)排列與組合從五個(gè)候選人中選出兩個(gè)代表把5本不同的書安排在書架上從五個(gè)候選人中選出兩個(gè)代表時(shí)，有10種可能的結(jié)果。把5本不同的書安排在書架上有120種方法選出-組合；安排-排列當(dāng)前第3頁\共有121頁\編于星期二\7點(diǎn)一、排列組合公式排列問題：從某個(gè)集合中有序地選取若干個(gè)元素的問題組合問題：從某個(gè)集合中無序地選取若干個(gè)元素的問題注意：可以重復(fù)不能重復(fù)當(dāng)前第4頁\共有121頁\編于星期二\7點(diǎn)排列無重排列可重排列從{1,2,…,9}中選取數(shù)字構(gòu)成四位數(shù)，使得每位數(shù)字都不同，有多少個(gè)？從{1,2,…,9}中選取數(shù)字構(gòu)成四位數(shù)，使得不同數(shù)位上的數(shù)字可以相同，有多少個(gè)？當(dāng)前第5頁\共有121頁\編于星期二\7點(diǎn)1、無重排列n個(gè)元素的r-無重排列數(shù)：排列的長度r計(jì)算（一般情形）：乘法原理r=n時(shí),n個(gè)元素的全排列r=0時(shí)r>n時(shí)當(dāng)前第6頁\共有121頁\編于星期二\7點(diǎn)2、可重排列n個(gè)元素的r-可重排列數(shù)計(jì)算（乘法原理）當(dāng)前第7頁\共有121頁\編于星期二\7點(diǎn)例題在1和10,000,000,000之間的一百億個(gè)數(shù)中，有多少個(gè)數(shù)含有數(shù)碼1？又有多少個(gè)數(shù)不含數(shù)碼1？不含1:910含1:1010-910+1當(dāng)前第8頁\共有121頁\編于星期二\7點(diǎn)例題一個(gè)二元序列是由一些0和1所組成的序列。n碼二元序列指該序列中數(shù)碼的個(gè)數(shù)為n。試問，含有偶數(shù)個(gè)0的n碼二元序列的個(gè)數(shù)是多少？2n-1考慮n碼四元序列，即以0,1,2和3為其數(shù)碼的序列。則含0和1的總個(gè)數(shù)為偶數(shù)的序列有多少個(gè)？4n/2當(dāng)前第9頁\共有121頁\編于星期二\7點(diǎn)例題求n碼四元序列中含有偶數(shù)個(gè)0的個(gè)數(shù)？當(dāng)前第10頁\共有121頁\編于星期二\7點(diǎn)放球問題設(shè)n≥r，把r個(gè)不同的球放入n個(gè)不同的盒子，這里每一盒最多只能裝一物，允許空盒。放球的方法數(shù)為多少？第一個(gè)球有n種選法，第二個(gè)球有n-1種，等等，乘法原理P(n,r)當(dāng)前第11頁\共有121頁\編于星期二\7點(diǎn)放球問題把r個(gè)不同的球放入n個(gè)不同的盒子，一個(gè)盒中可以放多個(gè)球，也允許空盒。放球的方法數(shù)為多少？第一個(gè)球有n種選法，第二個(gè)球有n種，等等，乘法原理nr這里n和r的大小沒有限制當(dāng)前第12頁\共有121頁\編于星期二\7點(diǎn)放球問題把r個(gè)不同的球放入n個(gè)不同的盒子，一個(gè)盒中可以放多個(gè)球，也允許空盒?？紤]每個(gè)盒子中球的次序。放球的方法數(shù)為多少？把這樣一個(gè)方法設(shè)想為r個(gè)不同的球和n-1個(gè)相同的盒間板的一個(gè)有序安排。C(r+n-1,n-1)=C(r+n-1,r)=F(n,r)另解：有n種方法放第一個(gè)球，第一個(gè)球放入一個(gè)盒后，可以把這個(gè)球當(dāng)成是一個(gè)添加的隔板，它把該盒分成兩個(gè)盒，因此放第二個(gè)球有n+1種方法。等等當(dāng)前第13頁\共有121頁\編于星期二\7點(diǎn)放球問題：例題今欲在五根旗桿上懸掛七面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？七部汽車通過五間收費(fèi)亭的方式數(shù)？當(dāng)前第14頁\共有121頁\編于星期二\7點(diǎn)組合無重組合可重組合從{a,b,c}中選取2個(gè)不同元素，選法數(shù)是多少？從{a,b,c}中選取5個(gè)元素，元素可以相同，選法數(shù)是多少？當(dāng)前第15頁\共有121頁\編于星期二\7點(diǎn)3、無重組合（Combination）n個(gè)元素的r-無重組合數(shù)無重組合數(shù)與無重排列數(shù)的關(guān)系計(jì)算r=0時(shí)r=n時(shí)r>n時(shí)當(dāng)前第16頁\共有121頁\編于星期二\7點(diǎn)組合數(shù)的推廣當(dāng)前第17頁\共有121頁\編于星期二\7點(diǎn)幾個(gè)記號(hào)下階乘函數(shù)上階乘函數(shù)當(dāng)前第18頁\共有121頁\編于星期二\7點(diǎn)計(jì)算當(dāng)前第19頁\共有121頁\編于星期二\7點(diǎn)例題如果一個(gè)凸十邊形無三條對(duì)角線在這個(gè)十邊形的內(nèi)部交于一點(diǎn)，問這些對(duì)角線被它們的交點(diǎn)分成多少條線段？當(dāng)前第20頁\共有121頁\編于星期二\7點(diǎn)多邊形當(dāng)前第21頁\共有121頁\編于星期二\7點(diǎn)例題對(duì)角線的條數(shù)為C(10,2)-10=45-10=35任選兩條對(duì)角線，可能相交在多邊形內(nèi)部，可能交點(diǎn)為多邊形的頂點(diǎn)，可能無交點(diǎn)（交點(diǎn)在多邊形外）任選四個(gè)頂點(diǎn)，對(duì)應(yīng)一個(gè)交點(diǎn)，每個(gè)對(duì)角線分成兩段每個(gè)對(duì)角線是一段35+C(10,4)×2=455當(dāng)前第22頁\共有121頁\編于星期二\7點(diǎn)例題C(5,2)-5+C(5,4)×2=15C(10,2)-10+C(10,4)×2=455C(4,2)-4+C(4,4)×2=4當(dāng)前第23頁\共有121頁\編于星期二\7點(diǎn)4、可重組合n個(gè)元素的r-可重組合例子計(jì)算一一對(duì)應(yīng)的思想當(dāng)前第24頁\共有121頁\編于星期二\7點(diǎn)推論方程x1+x2+…+xn=r的非負(fù)整數(shù)解的個(gè)數(shù)。n≤r時(shí)，此方程的正整數(shù)解的個(gè)數(shù)n元集合的r-可重組合數(shù)，要求每個(gè)元素至少出現(xiàn)一次。正整數(shù)r的n-長有序分拆的個(gè)數(shù)求x1+x2+x3+x4=20的整數(shù)解的數(shù)目，其中x1≥

3,x2≥1,x3≥0,x4≥5。當(dāng)前第25頁\共有121頁\編于星期二\7點(diǎn)例題從為數(shù)眾多的一分幣、二分幣、一角幣和二角幣中，可以有多少種方法選出六枚來？F(4,6)=C(4+6-1,6)=C(9,6)=84當(dāng)前第26頁\共有121頁\編于星期二\7點(diǎn)例題某糕點(diǎn)廠將8種糕點(diǎn)裝盒，若每盒有一打糕點(diǎn)，求市場上能買到多少種該廠出品的盒裝糕點(diǎn)？某糕點(diǎn)廠將8種糕點(diǎn)裝盒，若每盒有一打糕點(diǎn)，且要求每種糕點(diǎn)至少放一塊。求市場上能買到多少種該廠出品的盒裝糕點(diǎn)？當(dāng)前第27頁\共有121頁\編于星期二\7點(diǎn)例題搖三個(gè)不同的骰子的時(shí)候，可能的結(jié)果的個(gè)數(shù)是多少？63=216。如果這三個(gè)骰子是沒有區(qū)別的，則可能結(jié)果的個(gè)數(shù)是多少？從1,2,3,4,5,6這六個(gè)數(shù)中允許重復(fù)地選出三個(gè)數(shù)。F(6,3)=C(6+3-1,3)=56將r個(gè)骰子擲一次，總共可以擲出多少種不同結(jié)果？F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5)當(dāng)前第28頁\共有121頁\編于星期二\7點(diǎn)有約束條件的排列：引例用兩面紅旗、三面黃旗依次懸掛在一根旗桿上，問可以組成多少種不同的標(biāo)志？當(dāng)前第29頁\共有121頁\編于星期二\7點(diǎn)5、有約束條件的排列設(shè)有k個(gè)元素a1，a2，…，ak，由它們組成一個(gè)n-長的排列，其中對(duì)1≤i≤k，ai出現(xiàn)的次數(shù)為ni，n1+n2+…

+nk=n，求排列的總數(shù)。求解方法1求解方法2當(dāng)前第30頁\共有121頁\編于星期二\7點(diǎn)例題五條短劃和八個(gè)點(diǎn)可以安排成多少種不同的方式？如果只用這十三個(gè)短劃和點(diǎn)中的七個(gè)，則有多少種不同的方式？當(dāng)前第31頁\共有121頁\編于星期二\7點(diǎn)例題證明對(duì)任意正整數(shù)k,(k!)!能被(k!)(k-1)!整除。提示：k!個(gè)物體，其中k個(gè)物體屬于第一類，k個(gè)物體屬于第二類，…，k個(gè)物體屬于第(k-1)!類。當(dāng)前第32頁\共有121頁\編于星期二\7點(diǎn)推論多項(xiàng)式(x1+x2+…+xr)n的展開式中有

項(xiàng)，其中項(xiàng)的系數(shù)為

。當(dāng)前第33頁\共有121頁\編于星期二\7點(diǎn)例題數(shù)1400有多少個(gè)正因數(shù)？1400=23×

52×

7(3+1)(2+1)(1+1)=24當(dāng)前第34頁\共有121頁\編于星期二\7點(diǎn)放球問題設(shè)n≥r，把r個(gè)相同的球放入n個(gè)不同的盒子使得每盒至多裝一個(gè)球，方法數(shù)？選盒子即可C(n,r)當(dāng)前第35頁\共有121頁\編于星期二\7點(diǎn)放球問題把r個(gè)相同的球放入n個(gè)不同的盒子，每盒可以裝任意多個(gè)球，方法數(shù)？放這r個(gè)球，等價(jià)于從n個(gè)盒中選出r個(gè)來裝這r個(gè)球而允許諸盒重復(fù)選取。F(n,r)=C(n+r-1,r)另解：把分配這r個(gè)球入n個(gè)盒子設(shè)想為這r個(gè)球和n-1個(gè)隔板的一個(gè)排列。球是相同的，隔板也是相同的。C(n+r-1,r)當(dāng)前第36頁\共有121頁\編于星期二\7點(diǎn)放球問題設(shè)r≥n，把r個(gè)相同的球放入n個(gè)不同的盒子中，盒子中可以放入任意多個(gè)球，但不允許空盒，方法數(shù)？現(xiàn)在每個(gè)盒中放入一個(gè)球，再放剩下的r-n個(gè)球C((r-n)+n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)當(dāng)前第37頁\共有121頁\編于星期二\7點(diǎn)放球問題設(shè)r≥n，把r個(gè)相同的球放入n個(gè)不同的盒子中，要求每一盒至少包含q個(gè)球，方法數(shù)？現(xiàn)在每個(gè)盒中放入q個(gè)球，再放剩下的r-qn個(gè)球C((r-qn)+n-1,r-qn)=C(n-nq+r-1,r-nq)=C(n-nq+r-1,n-1)當(dāng)前第38頁\共有121頁\編于星期二\7點(diǎn)放球問題：例題今有五封不同的信要經(jīng)由一個(gè)訊道傳送。又有總共15個(gè)空白要插在這些信之間而使得每兩封信之間至少有三個(gè)空白。有多少種方法安排這些信和空白？信的安排5！對(duì)一種信的安排，有4個(gè)信件位置，安排15個(gè)空白，要求每個(gè)信件位置至少有三個(gè)空白。5！C(4-4×3+15-1,4-1)=5!×C(6,3)當(dāng)前第39頁\共有121頁\編于星期二\7點(diǎn)放球問題有n個(gè)球，其中第一種顏色n1個(gè)，第二種顏色n2個(gè)，…，第k種顏色nk個(gè)。將這n個(gè)球放入n個(gè)不同的盒中，每一個(gè)盒裝一個(gè)球。問分配方案數(shù)？等價(jià)于這n個(gè)球的排列數(shù)。另解：選盒子裝每種顏色的球。當(dāng)前第40頁\共有121頁\編于星期二\7點(diǎn)放球問題有r個(gè)球，其中第一種顏色n1個(gè)，第二種顏色n2個(gè)，…，第k種顏色nk個(gè)。將這r個(gè)球放入n個(gè)不同的盒中，每一個(gè)盒裝一個(gè)球（r≤n）。問分配方案數(shù)？方法一：先選盒子，再分配球。方法二：針對(duì)每種顏色的球選盒子。當(dāng)前第41頁\共有121頁\編于星期二\7點(diǎn)多重集合通常的“集合”具有無重性。在多重集中，同一個(gè)元素可以出現(xiàn)多次。{1,2,3}是一個(gè)集合，而{1,1,1,2,2,3}不是一個(gè)集合，而是一個(gè)多重集，簡記為{3·1,2·2,1·3}。計(jì)算多重集的勢時(shí)，出現(xiàn)多次的元素則需要按出現(xiàn)的次數(shù)計(jì)算。上面多重集的勢為6?？芍亟M合與可重排列可以看作是多重集的組合與排列問題。當(dāng)前第42頁\共有121頁\編于星期二\7點(diǎn)可重排列與可重組合n個(gè)元素{a1,a2,…,an}的r-無重組合(排列)可以看做多重集{1·a1,1·a2,…,1·an}的r-組合(排列)。n個(gè)元素{a1,a2,…,an}的r-可重組合(排列)可以看做多重集{∞·a1,∞·a2,…,∞·an}的r-組合(排列)。有限制的排列問題可以看做多重集{n1·a1,n2·a2,…,nk·ak}的全排列。當(dāng)前第43頁\共有121頁\編于星期二\7點(diǎn)分組與分堆固定分組：無序分組：分堆不定分組固定分組與分堆的區(qū)別是講不講組間的次序，只在各組元素個(gè)數(shù)相等時(shí)有區(qū)別固定分組與不定分組的區(qū)別是每個(gè)組的元素個(gè)數(shù)是不是確定，只在各組元素個(gè)數(shù)不等時(shí)才有區(qū)別。當(dāng)前第44頁\共有121頁\編于星期二\7點(diǎn)區(qū)分將12本書平均分給A,B,C,D四個(gè)學(xué)生，每人三本，有多少種分法？將12本書平均分成四堆有多少種分法？將12本書平均分給A,B,C,D四個(gè)學(xué)生，使得每人各得三本，有多少種分法？當(dāng)前第45頁\共有121頁\編于星期二\7點(diǎn)區(qū)分將12本書分給四個(gè)學(xué)生，使得A,B各得四本，C,D各得2本，有多少種分法？將12本書分成四堆，有兩堆各4本，另外兩堆各2本，有多少種分法？將12本書分給A,B,C,D四個(gè)學(xué)生，使得有兩個(gè)學(xué)生各得4本，有兩個(gè)學(xué)生各得2本，有多少種分法？當(dāng)前第46頁\共有121頁\編于星期二\7點(diǎn)區(qū)分將12本書分給四個(gè)學(xué)生，A得5本，B得4本，C得2本，D得1本，有多少種分法？將12本書分成四堆，其本數(shù)分別為5,4,2,1，有多少種分法？將12本書分給A,B,C,D四個(gè)學(xué)生，使得有1人得5本，有一人得4本，有1人得兩本，有1人得1本，有多少種分法？當(dāng)前第47頁\共有121頁\編于星期二\7點(diǎn)限距組合：引例書架上有1-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？當(dāng)前第48頁\共有121頁\編于星期二\7點(diǎn)6、限距組合設(shè)A={1,2,…,n}，它的任一r-無重組合均可以依自然順序排出a1,a2,…,ar，其中a1<a2<…<ar

。設(shè)k是非負(fù)整數(shù)，用f(k,n,r)表示A的一切滿足條件ai+1-ai≥k+1(1≤i≤r-1)的r-無重組合數(shù)，求f(k,n,r)。求解思想：一一對(duì)應(yīng)k=0時(shí)當(dāng)前第49頁\共有121頁\編于星期二\7點(diǎn)例題書架上有1-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？當(dāng)前第50頁\共有121頁\編于星期二\7點(diǎn)7、圓排列n個(gè)元素的r-無重圓排列數(shù)圓排列與線排列的區(qū)別計(jì)算當(dāng)前第51頁\共有121頁\編于星期二\7點(diǎn)例題例1把20個(gè)不同的釘子釘在鼓表面一周，訂釘子的方式有

種。例2把20個(gè)不同的珍珠串成項(xiàng)鏈，串項(xiàng)鏈的方式有

種。項(xiàng)鏈問題當(dāng)前第52頁\共有121頁\編于星期二\7點(diǎn)例從1到300間取出3個(gè)不同的數(shù)，使它們的和被3整除，有多少種取法？提示：將1到300這300個(gè)整數(shù)按照除以3的余數(shù)分成3組，考慮選出的3個(gè)數(shù)屬于哪些組。當(dāng)前第53頁\共有121頁\編于星期二\7點(diǎn)例下圖中有多少個(gè)矩形？當(dāng)前第54頁\共有121頁\編于星期二\7點(diǎn)映射的個(gè)數(shù)n元集X到m元集A的映射的個(gè)數(shù)將X看作物件的集合，A看作盒子的集合。則一個(gè)映射表示把物件放入盒子的一種安排。要求(1)每個(gè)物體都要放入某個(gè)盒子；(2)一個(gè)物體不得放入兩個(gè)盒子；(3)允許多個(gè)物體放入同一盒子；(4)可以剩有空盒子。若將X看作有標(biāo)號(hào)的位置的集合，A看作排在這些位置的字母的組合，則一個(gè)映射對(duì)應(yīng)一個(gè)長為n的字。則(1)字長必須為n；(2)一個(gè)位置只能放一個(gè)字母；(3)多個(gè)位置可以重復(fù)出現(xiàn)同一字母；(4)有些字母有可能不出現(xiàn)。當(dāng)前第55頁\共有121頁\編于星期二\7點(diǎn)例題n元集合X到m元集合A的映射的個(gè)數(shù)？將n個(gè)物體放在m個(gè)的盒子中的不同放法？n元集合X到m元集合A的單射的個(gè)數(shù)？把n個(gè)物體放入m個(gè)盒子，每個(gè)盒子至多放一個(gè)物體的安排有多少種？3個(gè)物體分放到4個(gè)不同的盒子中，要求每個(gè)盒子至多放一個(gè)物體的放法數(shù)？當(dāng)前第56頁\共有121頁\編于星期二\7點(diǎn)映射設(shè)映射f：{1,2,…,n}→{1,2,…,m}(n≤m)(1)若f是嚴(yán)格遞增的，則不同的f有多少個(gè)？(2)若f是不減的，則不同的f有多少個(gè)？當(dāng)前第57頁\共有121頁\編于星期二\7點(diǎn)例題1、從A={a,b,c}中任取兩個(gè)不同的字母構(gòu)成的字共有多少個(gè)？2、m元集合的n元子集的個(gè)數(shù)？3、平面上任三點(diǎn)都不共線的25個(gè)點(diǎn)，可形成多少條直線？可形成多少個(gè)三角形？當(dāng)前第58頁\共有121頁\編于星期二\7點(diǎn)例題用26個(gè)英文字母能構(gòu)成多少個(gè)含有3個(gè)、4個(gè)或5個(gè)元音的長為8位的單詞？（其中，一個(gè)字母出現(xiàn)在單詞中的次數(shù)不限）當(dāng)前第59頁\共有121頁\編于星期二\7點(diǎn)例題從一副52張撲克牌中任取13張得一手牌，在每一手牌中不考慮這13張牌的次序，則總共有多少手不同的牌？把一副52張撲克牌分給4個(gè)人，每人得13張，則總共有多少種不同的牌局？當(dāng)前第60頁\共有121頁\編于星期二\7點(diǎn)例題用4個(gè)a，4個(gè)b，2個(gè)c和2個(gè)d這12個(gè)字母能組成多少個(gè)具有12個(gè)字母的字？用字母a，b，c組成5個(gè)字母的字，每個(gè)字中a至多出現(xiàn)2次，b至多出現(xiàn)1次，c至多出現(xiàn)3次。這種字的個(gè)數(shù)是多少？當(dāng)前第61頁\共有121頁\編于星期二\7點(diǎn)例題單詞mississippi中字母的排列數(shù)為？求多重集{3·a,2·b,4·c}的8排列的個(gè)數(shù)？當(dāng)前第62頁\共有121頁\編于星期二\7點(diǎn)例題求26個(gè)英文字母的全排列中，任意兩個(gè)元音字母都不相鄰的方案數(shù)？當(dāng)前第63頁\共有121頁\編于星期二\7點(diǎn)例題Banach火柴盒問題：某數(shù)學(xué)家隨身攜帶A,B兩盒火柴，要用火柴時(shí)就隨意從其中一盒中取出一根。假定開始兩個(gè)火柴盒各放有n根火柴，問在某一次當(dāng)數(shù)學(xué)家發(fā)現(xiàn)拿出的那一個(gè)火柴盒變空時(shí)，另一盒中尚剩p(p<n)根火柴的概率是多少？當(dāng)前第64頁\共有121頁\編于星期二\7點(diǎn)例題10個(gè)人排成一排，其中有2個(gè)人不愿彼此挨著，求所有不同的排列的數(shù)目。10！-2×9！或8！A(9,2)=290304010個(gè)人圍一圓桌入座，其中有2個(gè)人不愿彼此挨著就座，求所有不同的圓排列的數(shù)目。9!-2×8!或7！A(8,2)=282240當(dāng)前第65頁\共有121頁\編于星期二\7點(diǎn)例題安排10個(gè)男生和5個(gè)女生排成一排，使任意2個(gè)女生都不相鄰的排法有多少種？A(10,10)A(11,5)安排10個(gè)男生和5個(gè)女生圍成圓圈入座，使任意2個(gè)女生都不相鄰的坐法有多少種？當(dāng)前第66頁\共有121頁\編于星期二\7點(diǎn)例從給定的6種不同的顏色中選不同的顏色將一個(gè)正方體的六個(gè)面染色，要求每個(gè)面染一種顏色，具有相同棱的面染成不同的顏色，則不同的染色方案有多少種？分析：一種顏色？兩種顏色？三種顏色？相對(duì)的面染成相同的顏色,只有一種方式C(6,3)當(dāng)前第67頁\共有121頁\編于星期二\7點(diǎn)四種顏色：五種顏色：六種顏色：C(6,4)C(4,2)C(6,5)C(5,1)3！/2C(6,6)C(5,1)3！當(dāng)前第68頁\共有121頁\編于星期二\7點(diǎn)例試求由1,3,5,7組成的數(shù)字不重復(fù)出現(xiàn)的整數(shù)的總和。分析：一位數(shù)1，3，5，7兩位數(shù)個(gè)(十)位數(shù)為1的兩位數(shù)的個(gè)數(shù)三位數(shù)個(gè)(十、百)位數(shù)為1的三位數(shù)的個(gè)數(shù)四位數(shù)個(gè)(十、百、千)位數(shù)為1的四位數(shù)的個(gè)數(shù)當(dāng)前第69頁\共有121頁\編于星期二\7點(diǎn)例假定把全部的5碼數(shù)印刷在紙條上，而一張紙條上印一個(gè)數(shù)。所謂5碼數(shù)是由0,1,2,…,9這十個(gè)數(shù)字中的5個(gè)數(shù)字組成的數(shù)，開頭的一個(gè)或者幾個(gè)可以為0，例如00102,00000都是5碼數(shù)，顯然有100000個(gè)這樣的5碼數(shù)。然而由于數(shù)字0,1,6,8,9被倒過來就成了0,1,9,8,6。而一張紙條可以從上下兩個(gè)方向正看和倒看，所以有些5碼數(shù)可以共用一張紙條，如89166與99168。于是我們的問題是要用多少個(gè)不同的紙條才能做出這些5碼數(shù)？當(dāng)前第70頁\共有121頁\編于星期二\7點(diǎn)01234567890

101倒過來886996當(dāng)前第71頁\共有121頁\編于星期二\7點(diǎn)1357813578倒過來

89166681898916668189不是5碼數(shù)仍是5碼數(shù)仍是5碼數(shù)但不是自己而且是自己當(dāng)前第72頁\共有121頁\編于星期二\7點(diǎn)5碼數(shù)共105個(gè)倒過來仍是5碼數(shù)的有55個(gè)倒過來不再是5碼數(shù)的有105—55個(gè)一個(gè)數(shù)一張紙條倒過來是自己的有3x52個(gè)倒過來不是自己的有55—3x52個(gè)一個(gè)數(shù)一張紙條兩個(gè)數(shù)共用一張紙條當(dāng)前第73頁\共有121頁\編于星期二\7點(diǎn)所以紙條的個(gè)數(shù)為(105—55)+3x52+(55—3x52)/2105—(55—3x52)/2=98475當(dāng)前第74頁\共有121頁\編于星期二\7點(diǎn)例甲、乙兩方各有7名隊(duì)員，按事先排好的順序出場參加圍棋擂臺(tái)賽。雙方先由1號(hào)參加比賽，負(fù)者被淘汰，勝者再與對(duì)方2號(hào)隊(duì)員比賽，…，直到有一方全部被淘汰，另一方獲得勝利，形成一種比賽過程。那么所有可能出現(xiàn)的比賽過程的種數(shù)為多少？當(dāng)前第75頁\共有121頁\編于星期二\7點(diǎn)甲乙箭頭指向誰，表示誰負(fù)甲方贏：這是的一個(gè)7-可重組合當(dāng)前第76頁\共有121頁\編于星期二\7點(diǎn)甲乙當(dāng)前第77頁\共有121頁\編于星期二\7點(diǎn)甲乙當(dāng)前第78頁\共有121頁\編于星期二\7點(diǎn)甲乙當(dāng)前第79頁\共有121頁\編于星期二\7點(diǎn)例某車站有6個(gè)進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？進(jìn)站口人2ABCDEF13456789任務(wù)：給每個(gè)人選擇進(jìn)站口，選擇進(jìn)站的次序？當(dāng)前第80頁\共有121頁\編于星期二\7點(diǎn)安排：ABCDEF16種方式1安排：27種方式222安排：38種方式3333安排：914種方式進(jìn)站方式種數(shù)為方法一：當(dāng)前第81頁\共有121頁\編于星期二\7點(diǎn)123456取213456789的一個(gè)全排列，和5個(gè)213456789對(duì)應(yīng)的進(jìn)站方式為：913456872方法二：當(dāng)前第82頁\共有121頁\編于星期二\7點(diǎn)ABCDEF進(jìn)站方式為：913456872213456789對(duì)應(yīng)的排列為：當(dāng)前第83頁\共有121頁\編于星期二\7點(diǎn)進(jìn)站方式種數(shù)為213456789的排列5個(gè)或14個(gè)位置取5個(gè)放方框(不講順序)，剩下的放人(將順序)當(dāng)前第84頁\共有121頁\編于星期二\7點(diǎn)方法三：先選車站，ABCDEF的9-可重組合AAACCDEEF再排人，213456789的排列213456789對(duì)應(yīng)的進(jìn)站方式為：ABCDEF913456872當(dāng)前第85頁\共有121頁\編于星期二\7點(diǎn)對(duì)比例某車站有6個(gè)進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？今欲在六根旗桿上懸掛九面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？當(dāng)前第86頁\共有121頁\編于星期二\7點(diǎn)例8個(gè)人兩兩配對(duì)分成4組有多少種方式？方法一給每個(gè)人配對(duì)方法二一對(duì)一對(duì)地選，注意會(huì)重復(fù)推廣：2n個(gè)人兩兩配對(duì)分成n組有多少種方式？當(dāng)前第87頁\共有121頁\編于星期二\7點(diǎn)非降路徑問題從點(diǎn)到達(dá)點(diǎn)的非降路徑當(dāng)前第88頁\共有121頁\編于星期二\7點(diǎn)非降路徑數(shù)由(0,0)到(m,n)的非降路徑數(shù)為

。由(a,b)到(m,n)的非降路徑數(shù)為

。由(0,0)到(m,n),再到(a,b)的非降路徑數(shù)

。當(dāng)前第89頁\共有121頁\編于星期二\7點(diǎn)例題從點(diǎn)(0,0)到達(dá)點(diǎn)(m,n)，其中m<n，要求中間所經(jīng)過的路程上的點(diǎn)(a,b)都滿足a<b。問有多少種不同的路徑？當(dāng)前第90頁\共有121頁\編于星期二\7點(diǎn)分析從(0,0)到(m,n)

的非降路徑

過對(duì)角線必過對(duì)角線一一對(duì)應(yīng)：反射(0,0)→(0,1)→(m,n)(0,0)→(1,0)→(m,n)不過對(duì)角線當(dāng)前第91頁\共有121頁\編于星期二\7點(diǎn)反射：從上向下看，找路徑與對(duì)角線交點(diǎn)的第一個(gè)點(diǎn)，關(guān)于對(duì)角線反射左下邊路徑，與右上的路徑組合成一條路徑。當(dāng)前第92頁\共有121頁\編于星期二\7點(diǎn)例題求從點(diǎn)(0,0)到達(dá)點(diǎn)(n,n)且不與直線y=x相交的非降路徑數(shù)？分析：上一例題的特殊情況當(dāng)前第93頁\共有121頁\編于星期二\7點(diǎn)例題一場音樂會(huì)的票價(jià)為50元/張，排隊(duì)買票的顧客中有n位持有50元的鈔票，m位持有100元的鈔票，售票處沒有準(zhǔn)備50元的零錢。試問有多少種排隊(duì)的方法，使購票能順利進(jìn)行，不出現(xiàn)找不開錢的狀況，假定每位顧客限買一張，每位顧客僅買票一張，而且n≥m。當(dāng)前第94頁\共有121頁\編于星期二\7點(diǎn)例題用(m+n)維0,1-行向量(a1,a2,…,am+n)表示一種購票排隊(duì)狀態(tài)，其中ai=1表示第i位持50元的鈔票，ai=0表示第i人持100元的鈔票。這樣的行向量有m個(gè)0，n個(gè)1，所以這樣的行向量共有C(m+n,m)個(gè)，每個(gè)行向量可以對(duì)應(yīng)從點(diǎn)(0,0)到點(diǎn)(m,n)的非降路徑。當(dāng)ai=1時(shí)，對(duì)應(yīng)路徑中的第i步沿y軸向上走一格，當(dāng)ai=0時(shí)，對(duì)應(yīng)路徑中的第i步沿x軸向右走一格。為了使購票順利進(jìn)行，每個(gè)路徑中的點(diǎn)(a,b)應(yīng)滿足a≤b。也就是每個(gè)路徑在直線y=x的上方且不穿過直線y=x，可以有交點(diǎn)。當(dāng)前第95頁\共有121頁\編于星期二\7點(diǎn)由于n≥m，也就是在直線y=x-1上方的所有路徑。從(0,0)到(m,n)的在直線y=x-1上方的非降路徑從(0,1)到(m,n+1)的在直線y=x上方的非降路徑從(0,0)到(m,n+1)的在直線y=x上方的非降路徑第n個(gè)Catalan數(shù)當(dāng)前第96頁\共有121頁\編于星期二\7點(diǎn)Catalan數(shù)第n個(gè)Catalan數(shù)當(dāng)前第97頁\共有121頁\編于星期二\7點(diǎn)Catalan數(shù)的組合學(xué)意義當(dāng)前第98頁\共有121頁\編于星期二\7點(diǎn)例題n個(gè)+1和n個(gè)-1所組成的序列中所有其前k項(xiàng)(k=1,2,…,2n)之和不小于0的序列的數(shù)目是多少？滿足條件的序列為好序列，不滿足條件的為壞序列。好序列數(shù)=序列總數(shù)-壞序列數(shù)。n個(gè)+1和n個(gè)-1所組成的壞序列與n+1個(gè)+1和n-1個(gè)-1所組成的序列一一對(duì)應(yīng)。當(dāng)前第99頁\共有121頁\編于星期二\7點(diǎn)例題對(duì)每個(gè)壞序列，總可以找到最小的正奇數(shù)，使得ak=-1且ak之前的+1和-1的個(gè)數(shù)相等。將這個(gè)壞序列中前k項(xiàng)的每一項(xiàng)取反號(hào)，其余部分保持不變。所得序列