《排列與組合2》教學(xué)課件

1、排列與組合2010信息學(xué)奧賽問題求解專題第1頁，共28頁。例1 從甲地到乙地,可以乘火車,也可以乘汽車,還可以乘輪船。一天中，火車有4班，汽車有2班，輪船有3班。那麼，一天中乘坐這些交通工具從甲地到乙地共有多少種不同的走法？解：因為一天中乘火車有4種走法，乘汽車有2種走法，乘輪船有3種走法，每一種走法都可以從甲地到乙地，因此，一天中乘坐這些交通工具從甲地到乙地共有 4+2+3=9 種不同的走法。第2頁，共28頁。加法原理： 做一件事，完成它可以有 n 類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法， ，在第n類辦法中有mn種不同的方法。那么完成這件事共有 N= m1

2、+ m2+ + mn 種不同的方法。第3頁，共28頁。 例2 由 A 村去 B 村的道路有3條，由 B 村去 C 村的道路 有2條。從 A 村經(jīng) B 村去 C 村，共有多少種不同的走法？解：從A 村去 B 村有3種不同的走法，按這3種走法中的每一種走法到達B村后，再從 B村到達C 村又有2種不同的走法。因此，從 A 村經(jīng) B 村去 C 村共有 3 2 = 6 種不同的走法。A村B村C村北北中南南第4頁，共28頁。乘法原理： 做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法， ，做第n步有mn種不同的方法。那么完成這件事共有 N= m1 m2 mn 種不同

3、的方法。 第5頁，共28頁。分類計數(shù)原理(加法原理) ：做一件事情，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，在第n類辦法中有mn。種不同的方法，那么完成這件事共有N=m1+m2+mn種不同的方法。分步計數(shù)原理（乘法原理） ：做一件事情，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，做第n步有mn種不同的方法，那么完成這件事有N=m1*m2*mn種不同的方法。分類計數(shù)原理與“分類”有關(guān)，各種方法相互獨立，用其中任何一種方法都可以完成這件事；分步計數(shù)原理與“分步”有關(guān)，各個步驟相互依存，只有各個步驟都完成了，這件事

4、才算完成第6頁，共28頁。解: 從書架上任取數(shù)學(xué)書與語文書各一本,可以分成兩個步驟完成： 第一步取一本數(shù)學(xué)書，有6種方法； 第二步取一本語文書，有5種方法。 根據(jù)乘法原理，得到不同的取法的種數(shù)是： N= m1 m2 = 65 = 30例1 書架上層放有 6 本不同的數(shù)學(xué)書，下層放有 5 本不同的語文書。 從中任取一本，共有多少種不同的取法？ 從中任取數(shù)學(xué)書與語文書各一本，共有多少種不同的取法？第7頁，共28頁。例2 有數(shù)字 1，2，3，4，5 可以組成多少個三位數(shù)（各位上的數(shù)字許重復(fù)）？解：要組成一個三位數(shù)可以分成三個步驟完成： 第一步確定百位上的數(shù)字，從5個數(shù)字中任選一個數(shù)字，共有5種選法；

5、 第二步確定十位上的數(shù)字，由于數(shù)字允許重復(fù)，這仍有5種選法； 第二步確定十位上的數(shù)字，同理，它也有5種選法。 根據(jù)乘法原理，得到組成的三位數(shù)的個數(shù)是： N = 5 5 5 = 53 = 125第8頁，共28頁。例3 有不同的語文書9本，不同的數(shù)學(xué)書7本，不同的物理書5本，從中任取兩種不同類的書，共有多少種不同的取法？解：每次取出的兩本書中： 含 1 本語文書和 1 本數(shù)學(xué)書的共有 9 7 = 63 種取法； 含 1 本數(shù)學(xué)書和 1 本物理書的共有 7 5 = 35 種取法； 含 1 本語文書和 1 本物理書的共有 9 5 = 45 種取法。由加法原理得 63 + 35 + 45 = 143第9

6、頁，共28頁。排列 排列的概念：從n個不同元素中，任取m(mn)個元素(這里的被取元素各不相同)，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列。排列數(shù)的定義：從n個不同元素中，任取m(mn)個元素的所有排列的個數(shù)叫做從n個元素中取出m個元素的排列數(shù)，用符號 表示。 第10頁，共28頁。排列數(shù)公式：全排列數(shù)：規(guī)定：0！1計算用證明用第11頁，共28頁。組合組合的概念：一般地，從n個不同元素中取出m(mn)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合組合數(shù)的概念：從n個不同元素中取出m(mn)個元素的所有組合的個數(shù)，叫做從n個不同元素中取出m個元素的組合數(shù)用符號

7、 表示第12頁，共28頁。組合組合數(shù)公式： 或 (n，mN，且mn) 組合數(shù)的性質(zhì)1： 規(guī)定： ：=1； 性質(zhì)2：第13頁，共28頁。常用解題方法及適用題目類型直接法：特殊元素法、特殊位置法（兩者適用某一個或幾個元素在指定的位置或不在指定的位置）捆綁法（兩個或兩個以上的元素必須相鄰）插空法 （兩個或兩個以上的元素必須不相鄰）擋板法（相同的元素分成若干部分，每部分至少一個）間接法（排除法）第14頁，共28頁。一、相鄰問題捆綁法 把題中規(guī)定相鄰的幾個元素并為一組（當(dāng)作一個元素）參與排列例1：A、B、C、D、E五人并排成一排，如果A、B必須相鄰且B在A的右邊，那么不同的排法有（）A60 B48 C3

8、6 D24分析：把A、B視為1人，且B固定在A的右邊，則本題相當(dāng)于4人全排列，即 24引申：如沒有說B要在A的右邊則A44A22第15頁，共28頁。二、相離問題插空法元素相離（即不相鄰）問題，可先把無位置要求的幾個元素全排列，再把規(guī)定相離的幾個元素插入上述幾個元素間的空位和兩端。例2：七個站成一排，如果甲、乙二人必須不相鄰，則排法有（）A1440 B3600 C4820 D4800分析：除甲、乙外，其余5人排列為種，再用甲、乙去插六個空位，有種，不同排法種數(shù)為 3600。A26第16頁，共28頁。三、定序問題對稱法在排列問題中限制某幾個元素必須保持一定的順序，可用對稱思想解題，先排后除， 。例

9、3：A、B、C、D、E五個站一排，B必須站A右邊，則不同的排法 （ ）A25 B60 C90 D120分析：五個全排列，B在A右邊和B在A左邊排法數(shù)相同，即 60。引例：晚會原定的5個節(jié)目已排成節(jié)目單，開演前又加了2個節(jié)目，若將這2個節(jié)目插入原節(jié)目單中，則不同的插法有（）種。分析：原定的5個節(jié)目順序已定，則不同的插法有第17頁，共28頁。四、定位問題優(yōu)先法某個（或幾個）元素要排在指定位置，可先排這個（或幾個）元素再排其他元素。例4：一個老師和四名學(xué)生排成一排，老師不在兩端，則不同的排法有（）種。分析：老師在中間3個位置上選一個位置有 種，四名同學(xué)在其余四個位置有 種，其 72種。第18頁，共2

10、8頁。五、多排問題單排法把元素排成幾排的問題，可歸納為一排考慮，再分段處理。例5：8人站前后2排，每排4人，其中某2人站在前排，某1人站在后排有（）種排法。分析：看成一排，某2個人在前半段4個位置中選排2個，有 種，某1人在后半段4個人位置中選一個有 種，其余5人在余下5個位上有種，故共有 5760種排法。第19頁，共28頁。六、亂座問題分步法把元素排列到指定號碼位置上，可先把某個元素按規(guī)定排入，第2步再排另一個元素，如此繼續(xù)下去，依次即可完成。例6：將數(shù)了1，2，3，4，填入標(biāo)號為1，2，3，4的四個方格，每格填一個數(shù)，則每個方格的標(biāo)號與所填數(shù)字均不相同的填法有（）種。分析：先把1填入方格，

11、符合條件有3種，第2步把被填入方格的對應(yīng)數(shù)字填入其他3個方格，又有3種方法，第3步填余下的2個數(shù)字，只有1種填法，故共有3319種。引申：n封裝入n個信封時全部裝錯的裝法總數(shù)為。通常稱為伯努利一歐拉錯裝信封問題，又稱為亂序排列，即把n個元素的排列a1，a2，L，an重新排列，使每個元素都不在原來的位置上的排列問題。第20頁，共28頁。 (NOIP 2002)在書架上放有編號為1，2，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時要求每本書都不能放在原來的位置上。例如：n=3時： 原來位置為：1 2 3 放回去時只能為：3 l 2或2 3 1這兩種問題：求當(dāng)n=5時滿足以上條件的放法共有

12、多少種?(不用列出每種放法)44 第21頁，共28頁。七、多元問題分類法元素多，取出的情況也有多種，可按結(jié)果要求，分成不相容幾類情況，分別計算，最后總計。例7：由0，1，2，3，4，5組成沒有重復(fù)數(shù)字的六位數(shù)，其中個位數(shù)字小于十位數(shù)字的共有（）個。分析：個位數(shù)字只能是0，1，2，3，4共有5種情況，分別有 個，合并總計300個。用排除法也行，6個數(shù)全排，去掉首位是零的，然后一半即可（A66-A55）/2=（6*5*4*3*2*1-5*4*3*2*1）/2=300第22頁，共28頁。八、“至少”問題間接法例8：從4臺甲型和5臺乙型電視機中任取3臺，其中至少要甲、乙電視各一臺，則不同取法共有（）種

13、。分析：至少各一臺反面就是分別只取一種型號，不取另一種型號，故 種。第23頁，共28頁。九、條件問題排除法 在被選總數(shù)中，只有一部分符合條件，可從總數(shù)中減去不合條件者。例9：正六邊形中心和頂點共7個點，以其中3個點為頂點的三角形共有（）個。分析：7點取3點有 種，但有3組3點共線，不構(gòu)成三角形，故 種。第24頁，共28頁。十、選排問題，先取后排法。從n類元素中取出符合題意的n個元素，再安排到一定位置上，可用先取后排法。例10：四個不同球放入編號1，2，3，4四個盒子中，則恰有一個空盒的放法共有（）種。分析：先取4個球中的2個為一組，另2組各1球有 種，然后排列，在4個盒中每次排3組有種，共有 144種。第25頁，共28頁。十一、指標(biāo)問題用“隔板法”例11：將10個保送生預(yù)選指標(biāo)分配給某重點中學(xué)高三年級六個班，每班至少一名，共有多少種分配方案？分析：將10個名額并成一排，名額之間有9個空，用5塊隔板插入9個空，就可將10個名額分成6部分，每一種插法就對應(yīng)一種分配方法，故有 種方案。注意：隔板法與插空法是不同的，隔板法只適用于相同元素的分配問題。第26頁，共2