奧數(shù)排列與組合

1、排列組合應(yīng)用題的教學(xué)設(shè)計(jì)致遠(yuǎn)高中 朱英 2007.3解決排列組合應(yīng)用題的基礎(chǔ)是 ：正確應(yīng)用兩個(gè)計(jì)數(shù)原理，分清排列和組合 的區(qū)別。引例 1 現(xiàn)有四個(gè)小組，第一組 7人，第二組 8人，第三組 9人，第四組 10人， 他們參加旅游活動(dòng)：（1）選其中一人為負(fù)責(zé)人，共有多少種不同的選法。（2）每組選一名組長(zhǎng)，共有多少種不同的選法 4 評(píng)述：本例指出正確應(yīng)用兩個(gè)計(jì)數(shù)原理。引例 2（1）平面內(nèi)有 10 個(gè)點(diǎn)，以其中每 2個(gè)點(diǎn)為端點(diǎn)的線段共有多少條？（2）平面內(nèi)有 10 個(gè)點(diǎn)，以其中每 2個(gè)點(diǎn)為端點(diǎn)的有向線段共有多少條？ 評(píng)述：本例指出排列和組合的區(qū)別。求解排列組合應(yīng)用題的困難 主要有三個(gè)因素的影響：1、限制

2、條件。 2、背景變化。 3、數(shù)學(xué)認(rèn)知結(jié)構(gòu) 排列組合應(yīng)用題可以歸結(jié)為四種類(lèi)型 ：第一個(gè)專(zhuān)題 排隊(duì)問(wèn)題 重點(diǎn)解決： 1、如何確定元素和位置的關(guān)系 元素及其所占的位置，這是排列組合問(wèn)題中的兩個(gè)基本要素。以元素為主， 分析各種可能性， 稱(chēng)為“元素分析法”；以位置為主， 分析各種可能性， 稱(chēng)為“位 置分析法”。例：3 封不同的信，有 4 個(gè)信箱可供投遞，共有多少種投信的方法？ 分析：這可以說(shuō)是一道較簡(jiǎn)單的排列組合的題目了， 但為什么有的同學(xué)能做出正 確的答案 43（種），而有的同學(xué)則做出容易錯(cuò)誤的答案 34 （種），而他們又錯(cuò)在哪 里呢？應(yīng)該是錯(cuò)在“元素”與“位置”上了 !法一：元素分析法 （以信為主

3、） 第一步：投第一封信，有 4 種不同的投法； 第二步：接著投第二封信，亦有 4 種不同的投法； 第三步：最后投第三封信，仍然有 4 種不同的投法。 因此，投信的方法共有： 43 （種）。法二：位置分析法 （以信箱為主 ） 第一類(lèi)：四個(gè)信箱中的某一個(gè)信箱有 3 封信，有投信方法 C14 （種）； 第二類(lèi)：四個(gè)信箱中的某一個(gè)信箱有 2 封信，另外的某一個(gè)信箱有 1 封信， 有投信方法 C32P42 種 。第三類(lèi)：四個(gè)信箱中的某三個(gè)信箱各有 1 封信，有投信方法 P43 （種）。 因此，投信的方法共有： 64 （種 ）小結(jié)：以上兩種方法的本質(zhì)還是“信”與“信箱”的對(duì)應(yīng)問(wèn)題。2、如何處理特殊條件特殊

4、條件優(yōu)先考慮。例：7 位同學(xué)站成一排，按下列要求各有多少種不同的排法； 甲站某一固定位置；甲站在中間，乙與甲相鄰；甲、乙相鄰； 甲、乙兩 人不能相鄰； 甲、乙、丙三人相鄰；甲、乙兩人不站在排頭和排尾；甲、 乙、丙三人中任何兩人都不相鄰；甲、乙兩人必須相鄰，且丙不站在排頭和排 尾。第二個(gè)專(zhuān)題 排列、組合交叉問(wèn)題重點(diǎn)解決：1、先選元素，后排序。例：3 個(gè)大人和 2 個(gè)小孩要過(guò)河，現(xiàn)有 3 條船，分別能載 3 個(gè)、2 個(gè)和 1 個(gè) 人，但這 5 個(gè)人要一次過(guò)去，且小孩要有大人陪著，問(wèn)有多少種過(guò)河的方法？ 分析：設(shè) 1 號(hào)船載 3 人， 2 號(hào)船載 2 人， 3 號(hào)船載 2 人，小孩顯然不能進(jìn)第 3

5、號(hào) 船，也不能二個(gè)同時(shí)進(jìn)第 2 號(hào)船。法一：從 “小孩”入手。第一類(lèi)： 2 個(gè)小孩同時(shí)進(jìn)第 1 號(hào)船，此時(shí)必須要有大人陪著另外2 個(gè)大人同時(shí)進(jìn)第 2 號(hào)船或分別進(jìn)第 2、 3 號(hào)船，先選 3 個(gè)大人之一進(jìn) 1 號(hào)船， 有 N1 C31 1 P22 9 （種 ）過(guò)河方法第二類(lèi)： 2 個(gè)小孩分別進(jìn)第 1、2 號(hào)船，此時(shí)第 2 號(hào)船上的小孩必須要有大人 陪著，另外2 個(gè)大人同時(shí)進(jìn)第 1 號(hào)船或分別進(jìn)第 1、 3 號(hào)船，有過(guò)河方法N2 P22C31 1 P22 18 （種）。因此，過(guò)河的方法共有：N N1 N2 9 18 27 （種）。法二：從 “船”入手第一類(lèi)：第 1 號(hào)船空一個(gè)位，此時(shí) 3 條船的

6、載人數(shù)分別為 2、2、1，故 2 個(gè) 小孩只能分別進(jìn)第 1、2 號(hào)船，有過(guò)河方法 N1 P22P33 12 （種）；第二類(lèi)：第 2 號(hào)船空一個(gè)位，此時(shí) 3 條船的載人數(shù)分別為 3、1、1，故 2 個(gè) 小孩只能同時(shí)進(jìn)第 1 號(hào)船，有過(guò)河方法 N2 P33 6 （種）；第三類(lèi)：第 3號(hào)船空一個(gè)位，此時(shí) 3條船的載人數(shù)分別為 3、2、0，故 2個(gè) 小孩同時(shí)進(jìn)第 1號(hào)船或分別進(jìn)第 1、2 號(hào)船，有過(guò)河方法 N3 C31 P22C32 90 （種）。因此，過(guò)河的方法共有：N N1 N2 N3 12 6 9 27 （ 種）。2、怎樣界定是排列還是組合例：身高不等的 7 名同學(xué)排成一排，要求中間的高，從中間

7、看兩邊，一個(gè) 比一個(gè)矮，這樣的排法有多少種？ 身高不等的 7 名同學(xué)排成一排，要求中間的高，兩邊次高，再兩邊次高， 如此下去，這樣的排法共有有多少種？答： c63 20種 p21 p21 p21 =8 種本來(lái)是組合題，與順序無(wú)關(guān)，但有些學(xué)生不加分析， 看到排隊(duì)就聯(lián)想排列， 這是一個(gè)誤區(qū)。至于也不全是排列問(wèn)題， 只是人自然有高低， 按人的高低順次 放兩邊就是了。又例： 7 名同學(xué)排成一排，甲、乙、丙這三人的順序定，則不同排法有多 少種？分析，三人的順序定，實(shí)質(zhì)是從 7 個(gè)位置中選出三個(gè)位置， 然后按規(guī)定的順 序放置這三人，其余 4 人在 4 個(gè)位置上全排列。故有排法 c73 p44 =840種。

8、3、枚舉法 三人互相傳球，由甲開(kāi)始傳球，并作為第一次傳球，經(jīng)過(guò) 5 次傳球后，球仍 回到甲手中，則不同的傳球方式共有（A） 6 種 （B）8 種 （C）0 種（D）12 種解：（枚舉法）該題新穎，要在考試短時(shí)間內(nèi)迅速獲得答案，考慮互傳次數(shù) 不多，所得選擇的答案數(shù)字也不大，只要按題意一一列舉即可。甲甲甲甲第三個(gè)專(zhuān)題 分堆問(wèn)題重點(diǎn)解決：1、均勻分堆和非均勻分堆關(guān)于這個(gè)問(wèn)題，課本 P146練習(xí) 10如此出現(xiàn)： 8 個(gè)籃球隊(duì)有 2個(gè)強(qiáng)隊(duì)，先任 意將這 8 各隊(duì)分成兩個(gè)組，（每組 4個(gè)隊(duì)）進(jìn)行比賽，這兩個(gè)強(qiáng)隊(duì)被分成在一個(gè) 小組的概率是多少？由于課本后面出現(xiàn)這樣的練習(xí)題， 所以前面應(yīng)對(duì)這些問(wèn)題有所分析，

9、尤其為什么 均勻分堆有出現(xiàn)重復(fù)？應(yīng)舉例說(shuō)明。例：有六編號(hào)不同的小球， 分成 3 堆，每堆兩個(gè) 分成 3 堆，一堆一個(gè)，一堆兩個(gè)，一堆三個(gè) 分成 3 堆，一堆一個(gè)，一堆一個(gè)，一堆四個(gè) 在、的條件下， 再分別給三個(gè)小朋友玩， 每人一堆， 有多少種分法？ 分析：、都是分堆，其中是三個(gè)均勻分堆，有 3！重復(fù)，是兩 個(gè)均勻分堆，有 2！重復(fù)，如此類(lèi)推。是非均勻分堆，不可能出現(xiàn)重復(fù)。在教 學(xué)中應(yīng)用數(shù)字表示球，通過(guò)列舉法說(shuō)明重復(fù)的可能，以及避免重復(fù)。例：有六編號(hào)不同的小球， 分成 3 堆，每堆兩個(gè) 分成 3 堆，一堆一個(gè)，一堆兩個(gè)，一堆三個(gè) 分成 3 堆，一堆一個(gè)，一堆一個(gè)，一堆四個(gè) 在、的條件下， 再分別

10、給三個(gè)小朋友玩， 每人一堆， 有多少種分法？ 分析：、都是分堆，其中是三個(gè)均勻分堆，有 3！重復(fù)，是兩 個(gè)均勻分堆，有 2！重復(fù)，如此類(lèi)推。是非均勻分堆，不可能出現(xiàn)重復(fù)。在教 學(xué)中應(yīng)用數(shù)字表示球，通 過(guò)列舉法說(shuō)明重復(fù)的可能，以及避免重復(fù)。2 2 1 2 4答案： C6C4 C61C52 C64再乘以 P332、為什么有3!重復(fù)，怎樣避免重復(fù)例：從 4 名男生、 5名女生中任選 3 人參加學(xué)代會(huì)，至少男生、女生各一名 的不同選法有多少種？有些學(xué)生這樣想：先從 4 人中選一人，再?gòu)?5 人中選一人，最后在剩下的 7 人中選一人， 結(jié)果是 C41C51C71 140 結(jié)果是錯(cuò)誤的。因?yàn)楹竺娴?7 人

11、與 前面已選的人可能出現(xiàn)重復(fù)，正確的答案是 C 42C51 C41C52 70 。又例：有 4個(gè)唱歌節(jié)目， 4個(gè)舞蹈節(jié)目， 2個(gè)小品排成一個(gè)節(jié)目單，但舞蹈 和小品要相隔，不同的編排有多少種方法？有些學(xué)生這樣想，先定位 4個(gè)唱歌，有 5個(gè)位插入小品兩個(gè)位， 此時(shí)有 7 個(gè)位再 插入 4 個(gè)舞蹈，故的表達(dá)式是 P44 P52 P74 。其實(shí)，這里又出現(xiàn)了重復(fù)，正確的列式是P66P74 2P55P74第四個(gè)專(zhuān)題 直接法和間接法的區(qū)別及運(yùn)用重點(diǎn)解決：1、選擇集合的元素有交集問(wèn)題 ； 例：七人并坐一排，要求甲不坐首位，乙不坐末位，共有幾種不同的坐法？ 法一：直接法第一類(lèi)：甲在第 2-6號(hào)位中選一而坐，接

12、著乙在第 1-6 位中余下的 5 個(gè)位中 擇一而坐，剩下的任意安排 N1 C51C51P55 3000（種）；第二類(lèi)：甲在第 7 號(hào)坐，剩下的任意安排，有坐法數(shù) N2 P66 720 （種）。因此，不同的坐法數(shù)共有 N N1 N2 3000 720 3720 （種）。法二：間接法七人并坐，共有坐法數(shù) P77 （種）。甲坐首位， 有 P66 種方法；乙坐末位， 亦有 P66 種方法。甲坐首位、乙坐末位都不符合題目要求，所以應(yīng)該從扣除， 但在扣除的過(guò)程中， 甲坐首位且乙坐末位的情況被扣除了 2 次，因此還須補(bǔ)回一 個(gè) P55。因此，不同的坐法數(shù)有 N P77 2P66 P55 3720 （種）2、選擇元素中有至少、至多等問(wèn)題。在 100 件產(chǎn)品中，有 98 件合格品， 2 件次品，從 100 見(jiàn)產(chǎn)品中任意抽取 3 件，（ 1）至少有一件是次品的抽法有多少種？（ 2）至多有一件次品的抽法有多 少種？ 答：（ 1）解法 1： C1200 C928 9604解法 2 ： C21C927 C22C917 9604（2） C938 C21C928 161602以上的處理，主