計數(shù)原理與排列組合課件

1、計數(shù)原理與排列組合基本原理組合排列排列數(shù)公式組合數(shù)公式應(yīng)用問題1、知識結(jié)構(gòu)一。復(fù)習(xí)回顧 2。分類記數(shù)原理，分步記數(shù)原理分類記數(shù)原理分步記數(shù)原理原理 完成一件事可以有完成一件事可以有n n類類辦法，在第一類中有辦法，在第一類中有m m1 1種不種不同的方法，在第二類中有同的方法，在第二類中有m m2 2種不同的方法，種不同的方法，在第，在第n n類辦法中有類辦法中有m mn n種不同的方種不同的方法，那么完成這件事共法，那么完成這件事共n= n= m m1 1+m+m2 2+m+mn n有種不同的方有種不同的方法。法。 完成一件事需要分成完成一件事需要分成n個個步驟，第一步有步驟，第一步有m1種

2、不同的種不同的方法，第二步有方法，第二步有m2種不同的種不同的方法，方法，第，第n步有步有mn種種不同的方法，那么完成這件不同的方法，那么完成這件事共事共n=m1m2mn有種不同的方法有種不同的方法。 區(qū)別 分類記數(shù)原理針對的是分類記數(shù)原理針對的是“分類分類”問題，其中各種方問題，其中各種方法相互獨立，用其中任何一法相互獨立，用其中任何一種方法都可完成這件事。種方法都可完成這件事。 分步記數(shù)原理針對的是分步記數(shù)原理針對的是“分步分步”問題，各步方法相問題，各步方法相互依存，只有各步都完成才互依存，只有各步都完成才能完成這件事。能完成這件事。 排列組合定義從從n個個不同不同元素中，任取元素中，任

3、取m(mn)個個不同不同元素按照元素按照一定順序排成一列，叫一定順序排成一列，叫做從做從n個不同元素中取出個不同元素中取出m個不同元素的一個個不同元素的一個排排列列。從從n個個不同不同的元素中，的元素中，任取任取m（mn）個）個不不同同的元素并成一組，的元素并成一組，叫做從叫做從n個不同的元素個不同的元素中取出中取出m個不同的元個不同的元素的一個素的一個組合組合。區(qū)別與順序有關(guān)與順序無關(guān)判定 看取出的兩個元素互換位置是否為同一種方看取出的兩個元素互換位置是否為同一種方法，若不是，則是排列問題；若是，則是組合。法，若不是，則是排列問題；若是，則是組合。公式) 1() 2)(1(mnnnnamn)

4、!(!mnn!) 1()2)(1(mmnnnnmnc!mmnn3。排列與組合 4。解排列組合問題基本思路排列組合問題有序無序排列組合分類或分步分類或分步直接法直接法間接法不易解不易解題型2 可重復(fù)元素排列問題【例【例2】五五名學(xué)生報名參加四項體育比賽，每人限報一名學(xué)生報名參加四項體育比賽，每人限報一項，報名方法的種數(shù)為多項，報名方法的種數(shù)為多 少？五名學(xué)生爭奪四項比少？五名學(xué)生爭奪四項比賽的冠軍賽的冠軍(冠軍不并列冠軍不并列)，獲得冠軍的可能性有多少，獲得冠軍的可能性有多少種？種？ 解答：解答：報報名的方法種數(shù)為名的方法種數(shù)為4444445(種種)獲得冠獲得冠軍的可能情況有軍的可能情況有555

5、554(種種). 方法小節(jié)：方法小節(jié)： 解決解決“允許重復(fù)排列問題允許重復(fù)排列問題”常用常用“住店法住店法”，要，要注意區(qū)分兩類元素：注意區(qū)分兩類元素：一類元素可以重復(fù)，另一類不一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的元素看作能重復(fù)，把不能重復(fù)的元素看作“客客”，能重復(fù)的，能重復(fù)的元素看作元素看作“店店”，再利用乘法原理直接求解。，再利用乘法原理直接求解?；A(chǔ)知識梳理基礎(chǔ)知識梳理二、題型與方法【例例3】如如圖，用圖，用5種不同的顏色給圖中種不同的顏色給圖中a、b、c、d四個區(qū)域涂色，規(guī)定每個區(qū)四個區(qū)域涂色，規(guī)定每個區(qū)域只涂一種顏色，相鄰區(qū)域顏色不同，域只涂一種顏色，相鄰區(qū)域顏色不同，求有

6、多少種不同的涂色方法？求有多少種不同的涂色方法？題型3 涂色問題 解法一解法一（分步法）如題圖分四個步驟來完成涂色這件（分步法）如題圖分四個步驟來完成涂色這件事需分為四步，第一步涂事需分為四步，第一步涂a區(qū)有區(qū)有5種涂法；第二步涂種涂法；第二步涂b有有4種方法；第三步涂種方法；第三步涂c有有3種方法；第四步涂種方法；第四步涂d有有3種方法種方法(還還可以使用涂可以使用涂a的顏色的顏色)，根據(jù)分步計數(shù)原理共有，根據(jù)分步計數(shù)原理共有5433180種涂色方法種涂色方法 2011高考導(dǎo)航高考導(dǎo)航解法二（分類法）：完成涂色的方法分為兩類，第一類：解法二（分類法）：完成涂色的方法分為兩類，第一類：四個區(qū)域

7、涂四種不同的顏色共有四個區(qū)域涂四種不同的顏色共有 120種涂法；種涂法； 第二類：四個區(qū)域涂三種不同的顏色，由于第二類：四個區(qū)域涂三種不同的顏色，由于a、d不不相鄰只能是相鄰只能是a、d兩區(qū)域顏色一樣，將兩區(qū)域顏色一樣，將a、d看做一個區(qū)看做一個區(qū)域，共域，共 60種涂法種涂法 由分類計數(shù)原理知共有涂法由分類計數(shù)原理知共有涂法12060180(種種)方法總結(jié)：方法總結(jié)： 對涂色問題，有兩種解法，法對涂色問題，有兩種解法，法1是逐區(qū)圖示法，注意不是逐區(qū)圖示法，注意不相鄰可同色相鄰可同色. 法法2根據(jù)用色多少分類法根據(jù)用色多少分類法. 題型4 排列中的“相鄰”、“不相鄰問題” 【例例4】 a1，a

8、2，a8共八個元素共八個元素，分別計算滿足下列，分別計算滿足下列條件的排列數(shù)條件的排列數(shù)(1)八個元素排成一排，且八個元素排成一排，且a1，a2，a3，a4四個元素排在一四個元素排在一起；起；(2)八個元素排成一排，且八個元素排成一排，且a1，a2，a3，a4四個元素互不相四個元素互不相鄰；鄰；(3)八個元素排成一排，且八個元素排成一排，且a1，a2，a3，a4四個元素互不相四個元素互不相鄰，并且鄰，并且a5，a6，a7，a8也互不相鄰；也互不相鄰；(4)排成前后兩排每排四個元素排成前后兩排每排四個元素解答：解答：(1)（捆綁法捆綁法）先將a1，a2，a3，a4四個元素看成一四個元素看成一個元

9、素個元素與與a5，a6，a7，a8排列一排，有排列一排，有 種排法，再排種排法，再排a1，a2，a3，a4有 不同排法，根據(jù)分步計數(shù)原理知滿足條件分步計數(shù)原理知滿足條件的排列數(shù)為的排列數(shù)為 2 880.55a44a55a44a (2)(插空法插空法）先排）先排a5，a6，a7，a8四個元素排成一排，四個元素排成一排，有有 種排法；再將元素種排法；再將元素a1，a2，a3，a4插入由插入由a5，a6，a7，a8間隔及兩端的五個位置中的四個，有間隔及兩端的五個位置中的四個，有 種排法，根據(jù)分種排法，根據(jù)分步計數(shù)原理知：滿足條件的排列數(shù)為步計數(shù)原理知：滿足條件的排列數(shù)為 2 880.44a45a44

10、a45a (3)先先排排a5，a6，a7，a8，；共有；共有 種排種排法；然后排法；然后排a1，a2，a3，a4排在排在或或中的中的共有共有2 種排法；根據(jù)分步計種排法；根據(jù)分步計數(shù)原理共有數(shù)原理共有 2 1 152種排法種排法(4)前排有前排有 種排法，后排有種排法，后排有 種排法，由分步計數(shù)原種排法，由分步計數(shù)原理知共有理知共有 8！種排法！種排法44a44a44a44a48a44a44a48a方法總結(jié) （1）若某些元素必須相鄰，常用捆綁法，即先把這幾個相鄰元素捆在一起看成一個元素，再與其他元素全排列，最后再考慮這幾個相鄰元素的順序。 （2）若某些元素不相鄰，常用插空法，即先將普通元素全排

11、列，然后再從排就的每兩個元素之間及兩端選出若干個空擋插入這些特殊元素。 (3)前后排問題，直排法.變式變式4 4個男個男同學(xué)，同學(xué)，3個女同學(xué)站成一排個女同學(xué)站成一排(1)3個女同學(xué)必須排在一起，有多少種不同的排法？個女同學(xué)必須排在一起，有多少種不同的排法？(2)任何兩個女同學(xué)彼此不相鄰，有多少種不同的排任何兩個女同學(xué)彼此不相鄰，有多少種不同的排法？法？(3)其中甲、乙兩同學(xué)之間必須恰有其中甲、乙兩同學(xué)之間必須恰有3人，有多少種不人，有多少種不同的排法？同的排法？(4)甲、乙兩人相鄰，但都不與丙相鄰，有多少種不甲、乙兩人相鄰，但都不與丙相鄰，有多少種不同的排法？同的排法？ (5)女同學(xué)從左到右

12、按高矮順序排，有多少種不同的排女同學(xué)從左到右按高矮順序排，有多少種不同的排法？法？(3個女生身高互不相等個女生身高互不相等)解答：解答：(1)3個女個女同學(xué)是特殊元素，我們先把她們排好，共同學(xué)是特殊元素，我們先把她們排好，共有有 種排法；由于種排法；由于3個女同學(xué)必須排在一起，我們可視排個女同學(xué)必須排在一起，我們可視排好的女同學(xué)為一整體，再與男同學(xué)排隊，這時是好的女同學(xué)為一整體，再與男同學(xué)排隊，這時是5個元素個元素的全排列，應(yīng)有的全排列，應(yīng)有 種排法，由分步計數(shù)的原理種排法，由分步計數(shù)的原理,有有 720種不同排法種不同排法(2)先將男生排好，共有先將男生排好，共有 種排法，再在這種排法，再在

13、這4個男生的中間個男生的中間及兩頭的及兩頭的5個空檔中插入個空檔中插入3個女生有個女生有 種方案，故符合條種方案，故符合條件的排法共有件的排法共有 1 440種不同排法種不同排法55a(3)甲、乙甲、乙2人先排好，有人先排好，有 種排法，再從余下種排法，再從余下5人中選人中選3人人排在甲、乙排在甲、乙2人中間，有人中間，有 種排法，這時把已排好的種排法，這時把已排好的5人視人視為一整體，與最后剩下的為一整體，與最后剩下的2人再排，又有人再排，又有 種排法，這樣種排法，這樣總共有總共有 720種不同排法種不同排法(4)先排甲、乙和丙先排甲、乙和丙3人以外的其他人以外的其他4人，有人，有 種排法；由種排法；由于甲、乙要相鄰，故再把甲、乙排好，有于甲、乙要相鄰，故再把甲、乙排好，有 種排法；最種排法；最后把甲、乙排好的這個整體與丙分別插入原先排好的后把甲、乙排