排列組合公式教師助手

1、排列組合公式排列組合公式 排列組合公式排列組合公式 非降路徑問題非降路徑問題 組合恒等式組合恒等式1學(xué)校教課排列與組合 從五個(gè)候選人中選出選出兩個(gè)代表 把5本不同的書安排安排在書架上 從五個(gè)候選人中選出兩個(gè)代表時(shí)，有10種可能的結(jié)果。 把5本不同的書安排在書架上有120種方法 選出-組合；安排-排列2學(xué)校教課一、排列排列組合組合公式 排列問題：從某個(gè)集合中有序有序地選取若干個(gè)元素的問題 組合問題：從某個(gè)集合中無序無序地選取若干個(gè)元素的問題 注意：可以重復(fù) 不能重復(fù)3學(xué)校教課排列 無重排列 可重排列 從1,2,9中選取數(shù)字構(gòu)成四位數(shù)，使得每位數(shù)字都不同，有多少個(gè)？ 從1,2,9中選取數(shù)字構(gòu)成四位

2、數(shù)，使得不同數(shù)位上的數(shù)字可以相同，有多少個(gè)？4學(xué)校教課1、 無重排列 n個(gè)元素的r-無重排列無重排列數(shù)： 排列的長度r 計(jì)算（一般情形）：乘法原理 r=n時(shí),n個(gè)元素的全排列 r=0時(shí) rn時(shí)5學(xué)校教課2、可重排列 n個(gè)元素的r-可重排列可重排列數(shù) 計(jì)算（乘法原理）6學(xué)校教課例題 在1和10,000,000,000之間的一百億個(gè)數(shù)中，有多少個(gè)數(shù)含有數(shù)碼1？又有多少個(gè)數(shù)不含數(shù)碼1？ 不含1:910 含1:1010-910+17學(xué)校教課例題 一個(gè)二元序列是由一些0和1所組成的序列。n碼二元序列指該序列中數(shù)碼的個(gè)數(shù)為n。試問，含有偶數(shù)個(gè)0的n碼二元序列的個(gè)數(shù)是多少？ 2n-1 考慮n碼四元序列，即以

3、0,1,2和3為其數(shù)碼的序列。則含0和1的總個(gè)數(shù)為偶數(shù)的序列有多少個(gè)？ 4n/28學(xué)校教課例題 求n碼四元序列中含有偶數(shù)個(gè)0的個(gè)數(shù)？9學(xué)校教課放球問題 設(shè)nr，把r個(gè)不同的球放入n個(gè)不同的盒子，這里每一盒最多只能裝一物，允許空盒。放球的方法數(shù)為多少？ 第一個(gè)球有n種選法，第二個(gè)球有n-1種，等等，乘法原理 p(n,r) 10學(xué)校教課放球問題 把r個(gè)不同的球放入n個(gè)不同的盒子，一個(gè)盒中可以放多個(gè)球，也允許空盒。放球的方法數(shù)為多少？ 第一個(gè)球有n種選法，第二個(gè)球有n種，等等，乘法原理 nr 這里n和r的大小沒有限制11學(xué)校教課放球問題 把r個(gè)不同的球放入n個(gè)不同的盒子，一個(gè)盒中可以放多個(gè)球，也允許

4、空盒。考慮每個(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種方法。等等12學(xué)校教課放球問題：例題 今欲在五根旗桿上懸掛七面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？ 七部汽車通過五間收費(fèi)亭的方式數(shù)？13學(xué)校教課組合 無重組合 可重組合 從a,b,c中選取2個(gè)不同元素，選法數(shù)是多少？ 從a,b,c中選取5個(gè)元

5、素，元素可以相同，選法數(shù)是多少？14學(xué)校教課3、無重組合（combination） n個(gè)元素的r-無重組合無重組合數(shù) 無重組合數(shù)與無重排列數(shù)的關(guān)系 計(jì)算 r=0時(shí) r=n時(shí) rn時(shí)15學(xué)校教課組合數(shù)的推廣rnc)!( !rnrn!) 1() 1(rrnnnrnrnc)!( !rnrn!) 1() 1(rrnnnrnczrr,0, 00, 10,!) 1() 1(rrrrrr16學(xué)校教課幾個(gè)記號(hào)) 1() 1(nxxxxn下階乘函數(shù)上階乘函數(shù)) 1() 1(nxxxxn) 1() 1(nn!) 1() 1(!nnnncnn17學(xué)校教課計(jì)算3213210215318學(xué)校教課例題 如果一個(gè)凸十邊形無

6、三條對(duì)角線在這個(gè)十邊形的內(nèi)部交于一點(diǎn)，問這些對(duì)角線被它們的交點(diǎn)分成多少條線段？19學(xué)校教課多邊形20學(xué)校教課例題 對(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=45521學(xué)校教課例題c(5,2)-5+c(5,4) 2=15c(10,2)-10+c(10,4) 2=455c(4,2)-4+c(4,4) 2=422學(xué)校教課4、可重組合 n個(gè)元素的r-可重組合可重組合 例子 計(jì)算 一一對(duì)應(yīng)的思想23學(xué)校教課推論

7、 方程x1+x2+xn=r 的非負(fù)整數(shù)解的個(gè)數(shù)。 nr時(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。24學(xué)校教課例題 從為數(shù)眾多的一分幣、二分幣、一角幣和二角幣中，可以有多少種方法選出六枚來？ f(4,6)=c(4+6-1,6)=c(9,6)=8425學(xué)校教課例題 某糕點(diǎn)廠將8種糕點(diǎn)裝盒，若每盒有一打糕點(diǎn)，求市場上能買到多少種該廠出品的盒裝糕點(diǎn)？ 某糕點(diǎn)廠將8種糕點(diǎn)裝盒，若每盒有一打糕點(diǎn)，且要求每種糕點(diǎn)至少放一塊。求市場上能買到多少種該

8、廠出品的盒裝糕點(diǎn)？26學(xué)校教課例題 搖三個(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)27學(xué)校教課有約束條件的排列：引例 用兩面紅旗、三面黃旗依次懸掛在一根旗桿上，問可以組成多少種不同的標(biāo)志？28學(xué)校教課5、有約束條件的排列 設(shè)有k個(gè)元素a1，a2，ak，由它們組成一個(gè)n-長的排列，其中對(duì)1ik，ai出現(xiàn)的次數(shù)

9、為ni，n1+n2 + +nk=n，求排列的總數(shù)。 求解方法1 求解方法229學(xué)校教課例題 五條短劃和八個(gè)點(diǎn)可以安排成多少種不同的方式？ 如果只用這十三個(gè)短劃和點(diǎn)中的七個(gè)，則有多少種不同的方式？! 8 ! 5!13! 7 ! 0! 7+! 6 ! 1! 7+! 5 ! 2! 7+! 4 ! 3! 7+! 3 ! 4! 7+! 2 ! 5! 730學(xué)校教課例題 證明對(duì)任意正整數(shù)k,(k!)!能被(k!)(k-1)!整除。 提示：k!個(gè)物體，其中k個(gè)物體屬于第一類，k個(gè)物體屬于第二類， ，k個(gè)物體屬于第(k-1)!類。31學(xué)校教課推論 多項(xiàng)式(x1+x2+xr)n的展開式中有 項(xiàng)，其中項(xiàng) 的系數(shù)為

10、 。rnrnnxxx21216321)532(xxx23231xxxnrxxx)(21rrrnrnnnnnnnnnrxxxnnnn21212121,21為非負(fù)整數(shù)32學(xué)校教課例題 數(shù)1400有多少個(gè)正因數(shù)？ 1400=23 52 7 (3+1)(2+1)(1+1)=2433學(xué)校教課放球問題 設(shè)nr，把r個(gè)相同的球放入n個(gè)不同的盒子使得每盒至多裝一個(gè)球，方法數(shù)？ 選盒子即可 c(n,r)34學(xué)校教課放球問題 把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è)

11、球入n個(gè)盒子設(shè)想為這r個(gè)球和n-1個(gè)隔板的一個(gè)排列。球是相同的，隔板也是相同的。 c(n+r-1,r)35學(xué)校教課放球問題 設(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)36學(xué)校教課放球問題 設(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)37學(xué)

12、校教課放球問題：例題 今有五封不同的信要經(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)38學(xué)校教課放球問題 有n個(gè)球，其中第一種顏色n1個(gè)，第二種顏色n2個(gè)， ，第k種顏色nk個(gè)。將這n個(gè)球放入n個(gè)不同的盒中，每一個(gè)盒裝一個(gè)球。問分配方案數(shù)？ 等價(jià)于這n個(gè)球的排列數(shù)。 另解：選盒子裝每種顏色的球。39學(xué)校教課放球問題 有r個(gè)球，其中第一種顏色n1個(gè)，第二種顏色n2個(gè)， ，第

13、k種顏色nk個(gè)。將這r個(gè)球放入n個(gè)不同的盒中，每一個(gè)盒裝一個(gè)球（rn）。問分配方案數(shù)？ 方法一：先選盒子，再分配球。 方法二：針對(duì)每種顏色的球選盒子。40學(xué)校教課多重集合 通常的“集合”具有無重性。 在多重集中，同一個(gè)元素可以出現(xiàn)多次。 1,2,3是一個(gè)集合，而1,1,1,2,2,3不是一個(gè)集合，而是一個(gè)多重集，簡記為31,22,13。 計(jì)算多重集的勢時(shí)，出現(xiàn)多次的元素則需要按出現(xiàn)的次數(shù)計(jì)算。上面多重集的勢為6。 可重組合與可重排列可以看作是多重集的組合與排列問題。41學(xué)校教課可重排列與可重組合 n個(gè)元素a1,a2, ,an的r-無重組合(排列)可以看做多重集1a1, 1 a2, , 1 an

14、的r-組合(排列) 。 n個(gè)元素a1,a2, ,an的r-可重組合(排列)可以看做多重集a1, a2, , an的r-組合(排列) 。 有限制的排列問題可以看做多重集n1a1, n2 a2, ,nk ak的全排列。42學(xué)校教課分組與分堆 固定分組： 無序分組：分堆 不定分組 固定分組與分堆的區(qū)別是講不講組間的次序，只在各組元素個(gè)數(shù)相等時(shí)有區(qū)別 固定分組與不定分組的區(qū)別是每個(gè)組的元素個(gè)數(shù)是不是確定，只在各組元素個(gè)數(shù)不等時(shí)才有區(qū)別。43學(xué)校教課區(qū)分 將12本書平均分給a,b,c,d四個(gè)學(xué)生，每人三本，有多少種分法？ 將12本書平均分成四堆有多少種分法？ 將12本書平均分給a,b,c,d四個(gè)學(xué)生，使

15、得每人各得三本，有多少種分法？44學(xué)校教課區(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本，有多少種分法？45學(xué)校教課區(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本，有多少種分法？46學(xué)校教課限距組合：引例 書架上有1

16、-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？47學(xué)校教課6、限距組合 設(shè)a=1,2,n，它的任一r-無重組合均可以依自然順序排出a1,a2, ,ar，其中a1a2 ar 。設(shè)k是非負(fù)整數(shù)，用f(k,n,r)表示a的一切滿足條件ai+1-aik+1(1ir-1)的r-無重組合數(shù)，求f(k,n,r)。 求解思想：一一對(duì)應(yīng) k=0時(shí)48學(xué)校教課例題 書架上有1-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？49學(xué)校教課7、圓排列 n個(gè)元素的r-無重圓排列數(shù) 圓排列與線排列的區(qū)別 計(jì)算50學(xué)校教課例題例1把20個(gè)不同的釘子釘在鼓表面一周，

17、訂釘子的方式有 種。例2把20個(gè)不同的珍珠串成項(xiàng)鏈，串項(xiàng)鏈的方式有 種。項(xiàng)鏈問題項(xiàng)鏈問題51學(xué)校教課例 從1到300間取出3個(gè)不同的數(shù)，使它們的和被3整除，有多少種取法？提示：將1到300這300個(gè)整數(shù)按照除以3的余數(shù)分成3組，考慮選出的3個(gè)數(shù)屬于哪些組。52學(xué)校教課例 下圖中有多少個(gè)矩形？53學(xué)校教課映射的個(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看作排在這

18、些位置的字母的組合，則一個(gè)映射對(duì)應(yīng)一個(gè)長為n的字。 則(1)字長必須為n；(2)一個(gè)位置只能放一個(gè)字母；(3)多個(gè)位置可以重復(fù)出現(xiàn)同一字母；(4)有些字母有可能不出現(xiàn)。54學(xué)校教課例題 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ù)？55學(xué)校教課映射 設(shè)映射f：1,2, ,n 1,2, ,m(nm) (1) 若f是嚴(yán)格遞增的，則不同的f有多少個(gè)？ (2) 若f是不減的，則不同的f有多少個(gè)？56學(xué)校

19、教課例題1、從a=a,b,c中任取兩個(gè)不同的字母構(gòu)成的字共有多少個(gè)？2、m元集合的n元子集的個(gè)數(shù)？3、平面上任三點(diǎn)都不共線的25個(gè)點(diǎn)，可形成多少條直線？可形成多少個(gè)三角形？57學(xué)校教課例題 用26個(gè)英文字母能構(gòu)成多少個(gè)含有3個(gè)、4個(gè)或5個(gè)元音的長為8位的單詞？（其中，一個(gè)字母出現(xiàn)在單詞中的次數(shù)不限）58學(xué)校教課例題 從一副52張撲克牌中任取13張得一手牌，在每一手牌中不考慮這13張牌的次序，則總共有多少手不同的牌？ 把一副52張撲克牌分給4個(gè)人，每人得13張，則總共有多少種不同的牌局？59學(xué)校教課例題 用4個(gè)a，4個(gè)b，2個(gè)c和2個(gè)d這12個(gè)字母能組成多少個(gè)具有12個(gè)字母的字？ 用字母a，b，

20、c組成5個(gè)字母的字，每個(gè)字中a至多出現(xiàn)2次，b至多出現(xiàn)1次，c至多出現(xiàn)3次。這種字的個(gè)數(shù)是多少？60學(xué)校教課例題 單詞mississippi中字母的排列數(shù)為？ 求多重集3a,2b,4c的8排列的個(gè)數(shù)？61學(xué)校教課例題 求26個(gè)英文字母的全排列中，任意兩個(gè)元音字母都不相鄰的方案數(shù)？62學(xué)校教課例題 banach火柴盒問題：某數(shù)學(xué)家隨身攜帶a,b兩盒火柴，要用火柴時(shí)就隨意從其中一盒中取出一根。假定開始兩個(gè)火柴盒各放有n根火柴，問在某一次當(dāng)數(shù)學(xué)家發(fā)現(xiàn)拿出的那一個(gè)火柴盒變空時(shí)，另一盒中尚剩p(pn)根火柴的概率是多少？63學(xué)校教課例題 10個(gè)人排成一排，其中有2個(gè)人不愿彼此挨著，求所有不同的排列的數(shù)目

21、。 10！-29！或 8！a(9,2)=2903040 10個(gè)人圍一圓桌入座，其中有2個(gè)人不愿彼此挨著就座，求所有不同的圓排列的數(shù)目。 9!-28!或7！a(8,2)=28224064學(xué)校教課例題 安排10個(gè)男生和5個(gè)女生排成一排，使任意2個(gè)女生都不相鄰的排法有多少種？ a(10,10)a(11,5) 安排10個(gè)男生和5個(gè)女生圍成圓圈入座，使任意2個(gè)女生都不相鄰的坐法有多少種？65學(xué)校教課例 從給定的6種不同的顏色中選不同的顏色將一個(gè)正方體的六個(gè)面染色，要求每個(gè)面染一種顏色，具有相同棱的面染成不同的顏色，則不同的染色方案有多少種？分析：一種顏色？兩種顏色？三種顏色？相對(duì)的面染成相同的顏色,只有

22、一種方式c(6,3)66學(xué)校教課四種顏色：五種顏色：六種顏色：c(6,4) c(4,2)c(6,5) c(5,1)3！/2c(6,6) c(5,1)3！67學(xué)校教課例 試求由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ù)68學(xué)校教課例 假定把全部的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ù)。然

23、而由于數(shù)字0,1,6,8,9被倒過來就成了0,1,9,8,6。而一張紙條可以從上下兩個(gè)方向正看和倒看，所以有些5碼數(shù)可以共用一張紙條，如89166與99168。于是我們的問題是要用多少個(gè)不同的紙條才能做出這些5碼數(shù)？69學(xué)校教課0 1 2 3 4 5 6 7 8 90 101 倒過來 8 8 6 9 9 670學(xué)校教課1357813578倒過來 89166681898916668189不是5碼數(shù)仍是5碼數(shù)仍是5碼數(shù)但不是自己而且是自己71學(xué)校教課5碼數(shù)共105個(gè)倒過來仍是5碼數(shù)的有55個(gè)倒過來不再是5碼數(shù)的有10555個(gè)一個(gè)數(shù)一張紙條倒過來是自己的有3x52個(gè)倒過來不是自己的有553x52個(gè)一

24、個(gè)數(shù)一張紙條兩個(gè)數(shù)共用一張紙條72學(xué)校教課所以紙條的個(gè)數(shù)為(10555)+ 3x52+ (553x52)/2105(553x52)/2=9847573學(xué)校教課例 甲、乙兩方各有7名隊(duì)員，按事先排好的順序出場參加圍棋擂臺(tái)賽。雙方先由1號(hào)參加比賽，負(fù)者被淘汰，勝者再與對(duì)方2號(hào)隊(duì)員比賽，直到有一方全部被淘汰，另一方獲得勝利，形成一種比賽過程。那么所有可能出現(xiàn)的比賽過程的種數(shù)為多少？74學(xué)校教課甲乙1a1b2a2b3a3b4a4b5a5b6a6b7a7b箭頭指向誰，表示誰負(fù)甲方贏：甲方贏：5a7a5a5a5a5a7a這是1234567,a a a a a a a的一個(gè)7-可重組合75學(xué)校教課5a7a5

25、a5a5a5a7a甲乙1a1b2a2b3a3b4a4b5a5b6a6b7a7b76學(xué)校教課甲乙1a1b2a2b3a3b4a4b5a5b6a6b7a7b6a6a6a6a6a6a7a77學(xué)校教課1a甲乙1a1b2a2b3a3b4a4b5a5b6a6b7a7b1a1a1a1a1a1a78學(xué)校教課例 某車站有6個(gè)進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？進(jìn)站口人2abcdef13456789任務(wù)：給每個(gè)人選擇進(jìn)站口，選擇進(jìn)站的次序？79學(xué)校教課安排 ：abcdef16種方式1安排 ：27種方式222安排 ：38種方式3333安排 ：914種方式進(jìn)站方式種數(shù)為6 7 814 145!=！方法一：80

26、學(xué)校教課123456取213456789的一個(gè)全排列，和5個(gè)213456789對(duì)應(yīng)的進(jìn)站方式為：913456872方法二：81學(xué)校教課abcdef進(jìn)站方式為：913456872213456789對(duì)應(yīng)的排列為：82學(xué)校教課進(jìn)站方式種數(shù)為141!1!1!5!！145!=！213456789的排列5個(gè)或14個(gè)位置取5個(gè)放方框(不講順序)，剩下的放人(將順序)5149!c 149!59！ ！14=5！83學(xué)校教課方法三： 先選車站，a b c d ef 的9-可重組合aaaccdeef再排人，213456789的排列213456789對(duì)應(yīng)的進(jìn)站方式為：abcdef91345687284學(xué)校教課對(duì)比 例

27、 某車站有6個(gè)進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？ 今欲在六根旗桿上懸掛九面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？85學(xué)校教課例 8個(gè)人 兩兩配對(duì)分成4組有多少種方式？128,a aa方法一 給每個(gè)人配對(duì)方法二 一對(duì)一對(duì)地選，注意會(huì)重復(fù)推廣：2n個(gè)人兩兩配對(duì)分成n組有多少種方式？86學(xué)校教課非降路徑問題從點(diǎn) 到達(dá)點(diǎn) 的非降路徑非降路徑(0,0)(2,3)87學(xué)校教課非降路徑數(shù) 由(0,0)到(m,n)的非降路徑數(shù)為 。 由(a,b)到(m,n)的非降路徑數(shù)為 。 由(0,0)到(m,n),再到(a,b) 的非降路徑數(shù) 。88學(xué)校教課例題 從點(diǎn)

28、(0,0)到達(dá)點(diǎn)(m,n)，其中mn，要求中間所經(jīng)過的路程上的點(diǎn)(a,b)都滿足ab。問有多少種不同的路徑？89學(xué)校教課分析從(0,0) 到(m,n) 的非降路徑 過對(duì)角線必過對(duì)角線一一對(duì)應(yīng)：反射(0,0) (0,1) (m,n)(0,0) (1,0) (m,n)不過對(duì)角線90學(xué)校教課反射：從上向下看，找路徑與對(duì)角線交點(diǎn)的第一個(gè)點(diǎn)，關(guān)于對(duì)角線反射左下邊路徑，與右上的路徑組合成一條路徑。91學(xué)校教課例題 求從點(diǎn)(0,0)到達(dá)點(diǎn)(n,n)且不與直線y=x相交的非降路徑數(shù)？ 分析：上一例題的特殊情況92學(xué)校教課例題 一場音樂會(huì)的票價(jià)為50元/張，排隊(duì)買票的顧客中有n位持有50元的鈔票，m位持有100

29、元的鈔票，售票處沒有準(zhǔn)備50元的零錢。試問有多少種排隊(duì)的方法，使購票能順利進(jìn)行，不出現(xiàn)找不開錢的狀況，假定每位顧客限買一張，每位顧客僅買票一張，而且nm。93學(xué)校教課例題 用(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,

30、b)應(yīng)滿足ab。也就是每個(gè)路徑在直線y=x的上方且不穿過直線 y=x，可以有交點(diǎn)。94學(xué)校教課 由于nm ，也就是在直線y=x-1上方的所有路徑。 從(0,0)到(m,n)的在直線y=x-1上方的非降路徑 從(0,1)到(m,n+1)的在直線y=x上方的非降路徑 從(0,0)到(m,n+1)的在直線y=x上方的非降路徑1yx=-第n個(gè)catalan數(shù)1mnmmnmnm 122nnnn95學(xué)校教課catalan數(shù) 第n個(gè)catalan數(shù)122nnnncnnnn21196學(xué)校教課catalan數(shù)的組合學(xué)意義97學(xué)校教課例題 n個(gè)+1和n個(gè)-1所組成的序列中所有其前k項(xiàng)(k=1,2, ,2n)之和不

31、小于0的序列的數(shù)目是多少？ 滿足條件的序列為好序列，不滿足條件的為壞序列。 好序列數(shù)=序列總數(shù)-壞序列數(shù)。 n個(gè)+1和n個(gè)-1所組成的壞序列與n+1個(gè)+1和n-1個(gè)-1所組成的序列一一對(duì)應(yīng)。98學(xué)校教課例題 對(duì)每個(gè)壞序列，總可以找到最小的正奇數(shù)，使得ak=-1且ak之前的+1和-1的個(gè)數(shù)相等。將這個(gè)壞序列中前k項(xiàng)的每一項(xiàng)取反號(hào)，其余部分保持不變。所得序列為n+1個(gè)+1和n-1個(gè)-1組成的序列。 -1,-1,1,1,-1,1變?yōu)?,-1,1,1,-1,1 反之， 對(duì)任一由n+1個(gè)+1和n-1個(gè)-1組成的序列，從左到右掃描，當(dāng)+1的個(gè)數(shù)第一次比-1的個(gè)數(shù)多1時(shí)就把這些掃描到的項(xiàng)全部取反號(hào)，其余項(xiàng)不變，結(jié)果得到滿足要求的壞序列。 1,-1,1,1,-1,1變?yōu)?1,-1,1,1,-1,199學(xué)校教課二項(xiàng)式定理nyx)( )(yxnrxxx)(21nx)1 ( 100學(xué)校教課組合恒等式組合數(shù)組合恒等式：由組合數(shù)構(gòu)成的恒等式組合數(shù)的大小關(guān)系knn為奇數(shù)n為偶數(shù)101學(xué)校教課1.證明一：計(jì)算證明二：組合分析法knk