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

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

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

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

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

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

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

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

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

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

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

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

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

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