2012江蘇省數(shù)學競賽《提優(yōu)教程》教案：第57講 排列與組合

《2012江蘇省數(shù)學競賽《提優(yōu)教程》教案：第57講 排列與組合》由會員分享，可在線閱讀，更多相關(guān)《2012江蘇省數(shù)學競賽《提優(yōu)教程》教案：第57講 排列與組合（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 第 講 排列與組合 本節(jié)主要有：排列組合公式及應用；處理排列組合問題的常用方法：如插空法、捆綁法等；可重復排列及圓排列公式等基本內(nèi)容． A類例題 例1四個不同的小球放入編號1、2、3、4、的四個盒中，則恰有一個空盒的放法有____種。 分析 排列組合中諸如把教師醫(yī)生分到各所學校；把不同的小球放入盒中等問題都可以歸類為分組問題，分組問題解題的原則是：“分組先分堆”． 解 把4個球分成“2、1、1”三堆，有種分法，把三堆球分別放入四個盒子的任三個中，有種放法，由乘法原理，恰有一個空盒的放法共有·=144種． 說明：本題也可以分類討論求解，若1號盒空，2號盒放二個球，3

2、、4號盒各放一個球有=12種放法；同理，若1號盒空，3號盒放2個球，2、4號盒各放一個球也是12種放法；1號盒空，4號盒放2個球，2、3號盒各放一個球同樣是12種放法。所以，1號盒空共有12×3 = 36種放法。故滿足題設的總放法種數(shù)為4×36 = 144種。 例2 6名同學排成一排。 （1）其中甲、乙兩個必須排在一起的不同排法有______種.(1997年全國高考題) （2）甲乙兩人不能相鄰的排法有______種． 分析 排列組合中，處理“在與不在”、“鄰與不鄰”、“接與不接”等問題時，常常利用捆綁法或插空法． 解⑴把甲、乙兩人看作1人，這樣6個人可看成5個人，共有種排法，甲、乙

3、兩人有2種順序，故共有·種． ⑵ 先排其他4名同學，有種，再把甲乙兩人插入到4名同學的5個空擋中有種，所以共有·=480種． 情景再現(xiàn) 1．3名醫(yī)生和6名護士被分配到3所學校為學生體檢，每校分配1名醫(yī)生和2名護士，不同的分配方式共有 （ ） A．90種 B．180種 C．270種 D．540種 (1998年全國高考題) 2．某校從5名優(yōu)秀學生干部

4、中選出4人分別參加“資源”、“生態(tài)”和“環(huán)保”三個夏令營，要求每一個夏令營活動至少有選出的一人參加，且每人只參加一個夏令營活動，則不同的參加方案有（ ）種 A．90 B．180 C．270 D．540 B類例題 例3 在正方體的8個頂點，12條棱的中點，6個面的中心及正方體的中心共27個點中，共線的三點組的個數(shù)是 A 57 B 49 C 43

5、 D 37 (1998年全國數(shù)學聯(lián)賽) 分析 正方體中，共線三點組的兩個端點可能有三種情形：①兩端點都是頂點；②兩端點都是面的中心；③兩端點都是棱的中點，除此之外沒有別的情形． 解 兩端點都是頂點的共線組有個，兩端點都是面的中心的共線組有3個，兩端點都是棱的中點的共線組有個。所以滿足條件的共線組共有49個． 說明：分類討論是解決較復雜的排列組合問題的常用思想，分類討論的關(guān)鍵是找到合適的分類標準，做到不重不漏。 例4 某城市在中心廣場建造一個花圃，花圃分為6個部分（如右圖所示），現(xiàn)要栽種4種不同顏色的花，每部分栽種 一種且相鄰部分不能栽種同樣顏色的花，

6、不同的栽種方法有______種. （2003年江蘇高考題） 分析 本題是近幾年出現(xiàn)的排列組合問題中難度最大的問題之一。基本思想是運用分步記數(shù)原理。 解 如圖所示，把花壇視為一個圓環(huán)，先排區(qū)域1，有種.由于1與其余5個位置均相鄰，故其余5個位置共有3種顏色可選．由任兩個相鄰位置不能同色，故必有2種顏色各種兩塊地，第一種顏色只有一塊地，有種方法，另兩種顏色種4個位置，只有兩種選擇，故共有種. 例5．在某次乒乓球單打比賽中，原計劃每兩名選手恰比賽一場，但有3名選手各比賽了2場之后就退出了，這樣，全部比賽只進行了50場。那么，上述3名選手之間的比賽場數(shù)是 A．0

7、 B．1 C．2 D．3 （1999全國聯(lián)賽） 分析 3名選手共比賽了6場，設他們之間比賽了x場，故只有這3名選手參加的比賽共6－x場． 解 設三名選手之間的比賽為x場，共有n名選手參賽，由題得50 = ,即 ，由于0≤x≤3，經(jīng)檢驗知，僅當 x= 1時，n = 13為正整數(shù)，故選B． 說明 求解簡單的二元一次不定方程時，可逐個代入檢驗是否滿足題設. 例6 四面體的頂點和棱的中點共10個點，取4個不共面的點，不同的取法有 （ ） A．150種 B．147種 C．144種 D．141種 分

8、析 從所有的取法中減去共面的取法。其中4點共面的情形有三類：第一類，取出的4個點位于四面體的同一個面內(nèi)有種；第二類，取任一條棱上的3個點及該棱對棱中點，共6種；第三類，由中位線構(gòu)成的平行四邊形，兩組對邊分別平行于四面體相對的兩條棱，有3種． 解 由上述分析知共有種． 說明 “排除法”是常用方法之一，其難點在于排除那些不合條件的組合。 情景再現(xiàn) 3．如圖，點p1，p2，…，p10分別是四面體頂點或棱的中點。那么，在同一平面上的四點組(p1，pi，pj，pk)(1 < i < j ≤10) 有_______個. （2002年全國聯(lián)賽）

9、 4．四邊形ABCD被其對角線分為4個不同的三角形△OAB、△OBC、△OCD、△OAD（O為對角線的交點），若每個三角形用4種顏色的一種染色，那么出現(xiàn)相鄰三角形均不同色的四邊形的概率是 （ ） A. B. C. D. 5．某賽季足球比賽的計分規(guī)則是：勝一場，得3分；平一場，得1分；

10、負一場，得0分，一球隊打完15場，積33分。若不考慮順序，該隊勝、負、平的情況共有 A．3種 B．4種 C．5種 D．6種 6．原有m個同學準備在暑假中開展通信活動，每人都必須給另外(m-1)個同學寫一封信，后來又有n個同學對這個活動感興趣，若已知n > 1，且由于增加了n個同學而又多寫了74封信，則原有同學的人數(shù)m = ________________. C類例題 例7 8個女孩和25個男孩圍成一圈，任何兩個女孩之間至少站兩個男孩，問共有多少種不同的排列方法（只要把圈旋轉(zhuǎn)一下就重合的排法認為是相同的）.（1990年全國聯(lián)賽） 分析 以1個女孩和

11、2個男孩為一組，且使女孩恰好站在兩個男孩中間，余下的9個男孩和這8個組被看成是17個元素，顯然這17個元素任意的圓排列是滿足題意的． 解 先從25個男孩中選出9個男孩共有種可能。其次，上述17個元素的圓排列數(shù)為種. 再次，分在8個組內(nèi)的16個男孩在16個位置上的排列是，所以總的排列方法數(shù)為： ． 鏈接 1．在A={a1，a2，…，an}的n個元素中，每次取出r個元素排在一個圓環(huán)上，叫做一個圓排列，圓排列有三個特點：第一，無頭無尾；第二，按同一方向旋轉(zhuǎn)后仍是同一圓排列；第三，兩個圓排列只有在元素不同或者元素相同，但元素之間的順序不同，才是不同的圓排列. 2．圓排列計數(shù)公式：從n個元素

12、中取r個不同的元素進行圓排列，圓排列數(shù)為 特別地，當r = n時，圓排列數(shù)為(n-1)！ 3．項鏈問題：從n個相異的珠子中，每次取出r顆穿成一個項鏈，因其正反相對的兩個圓排列在穿成一個項鏈的完全相同，故項鏈數(shù)為 例8 試求從集合A={1，2，…，n}到集合B={1，2，…，m}的映射的個數(shù). 分析 在兩個集合之間建立映射本質(zhì)上是給集合A中的元素分步找象． 解 給A中元素分別找象，元素1有m種找法，元素2有m種找法，…，元素n有m種找法，故從A到B的映射的個數(shù)為mn． 鏈接：允許元素重復出現(xiàn)的排列，叫做可重復排列，在m個不同的元素里，每次取出n個元素，元素可重復出現(xiàn)，按一定的次

13、序排成一排的排列數(shù)為mn. 例9 整數(shù)1，2，…，n的排列滿足：每個數(shù)或者大于它之前的所有數(shù)，或者小于它之前的所有數(shù). 試問有多少個這樣的排列？（第21屆加拿大中學生數(shù)學競賽） 分析 由特殊到一般，找出遞推關(guān)系式． 解 記所求的排列的個數(shù)是an. 顯然，a1 = 1. 對于n≥2，考慮最大的數(shù)n，如果n排在第i位，則它之后的（n –i）個數(shù)排序完全確定，即只能是n – i，n – i – 1，…，1；而它之前的(i-1)個數(shù)有ai-1種排法，考慮到n的所有不同的位置，由加法原理知 an = 1 + a1 + a2 + … + an-1， 于是，an-1 = 1 + a1

14、+ a2 + … + an-2. 有an = 2an-1，又a1 = 1 故an = 2n-1． 情景再現(xiàn) 7．某城市有7條南北向的街，5條東西向的街，如果從城市的O點走向A點，最短的走法有多少種？ 8．用6個白珠、8個黑珠、一個紅珠串成一串，問共有多少種不同的串法？ 9．有數(shù)學、物理、文學3個課外活動小組，6個同學報名，每人限報一組，一共有多少種報名的方法？ 習題17 A 1．8次射擊，命中3次，其中恰有2次連續(xù)命中的情形共有________種。（1998年湖南聯(lián)賽） 2．2名醫(yī)生和4名護士被

15、分配到2所學校為學生體檢，每校分配10名醫(yī)生和2名護士，不同的分配方法共有 （ ） A．6種 B．12種 C．18種 D．24種 （1998年全國高考題） 3．如圖，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著色方法共有_________種。 4．正六邊形的中心和頂點共7個點，以其中3個點為頂點的三角形有_______個。 5．n個后乒乓球運動員(n≥4)，每兩個人都可以

16、組成一對雙打選手，從中選出兩對的選法有 （ ） A．3種 B．6種 C．3種 D．(6+3)種 6．已知兩個實數(shù)集合A={a1，a2，…，a100}與B={b1，b2，…，b50}，若從A到B的映射f使得B中每個元素都有原像，且f(a1) ≤ f(a2) ≤ …≤ f(a100)，則這樣的映射共有（ ）個 A．

17、 B． C． D． B 7．在一個正六邊形的六個區(qū)域種觀賞植物，如圖，要求同一塊中種同一植物，相鄰的兩塊種不同的植物，現(xiàn)有4種不同的植物可供選擇，則有_______種栽種方案. 8．在1，2，3，4，5的排列a1，a2，a3，a4，a5中，滿足條件a1 < a2，a2 > a3，a3 < a4，a4 > a5的排列個數(shù)是 （ ） A．8 B．10 C．14 D．

18、16 9．“漸升數(shù)”是指每個數(shù)字比其左邊的數(shù)字大的正整數(shù)，如34689，已知有個五位“漸升數(shù)”，若把這些數(shù)按從小到大的順序排列，則第100個數(shù)是______________。 10．把1996個不加區(qū)別的小球放在10個不同的盒子里，使得第i個盒子中至少有i個球（i＝1，2，…，10），問不同放法的總數(shù)是多少？ C 11．用六種不同顏色中的幾種染一個正方體各面，要求相鄰兩面不同色，問有多少種不同染色法？（兩個染色正方形，如能通過轉(zhuǎn)動、翻身使二者各面顏色對應相等，則認為是相同染色法）（1996年全國聯(lián)賽） 12．4對夫婦去看電影，8人生成一排，若每位女性的鄰座只能是丈夫或另外的女性，共有

19、多少種坐法？ 本節(jié)“情景再現(xiàn)”解答： 1．A·C·C＝540種 2．先選出4人有C種選法，把4人分成“2，1，1”三堆，有種分法，共有C××A＝180種。 3．首先，在每個側(cè)面上除P1點外尚有五個點，其中任意三點添加P1后組成的4點組都在同一平面，這樣的三點組有C個，三個側(cè)面共有3 C個。其次，含P1的每條棱上的三點組添加底面與它異面的那條棱上的中點組成的四點也在一個平面上，這樣的四點組有3個，故共有3 C＋3＝33個。 4．分別以S1、S2、S3、S4依次記 △OAB、△OBC、△OCD、△ODA，顯然，若不考慮相鄰三角形

20、不同色的要求，則共 有44＝256種涂法。 下面先對S1和S3涂色 i）S1和S3同色，它們共有4種選擇，對每一對選擇，S2和S4各有3種選擇，所以此時共有4×3×3＝36種不同涂法。 ii）S1和S3不同色，它們共有C＝12種選擇，對每一種選擇，S2和S4各有3種選擇，所以此時共有12×2×2＝48種不同涂法。 所以相鄰三角形均不同色的四邊形出現(xiàn)的概率為 5．設勝x場，平y(tǒng)場，則負（15―x―y）場，得3x＋y＝33，又y＝33－3x≥0 ∴x≤11，且x＋y≤15，共有；；三種情形。 6．由題得C－C＝74 即－＝74，即n(2m＋n－1)＝148

21、＝22×37，由于n與2m＋n－1有不同的奇偶性，故只能解得n＝4，2m＋3＝37有m＝17整數(shù)解。 7．每條東西向的街被分成6段，每段不妨都用相同的a表示，共有6個a。每條南北向的街被分成4段，用4個b表示，含有6個a和4個b的一種全排列，對應于從0到A的一種走法。例如排列aaabaabab，對應于上圖中箭頭所示的走法，故走法有＝210種。 8．這是一個圓排列問題，如固定紅珠，則為線排列，故除紅珠外其余的14個珠子共有N1＝＝3003種串法，14個珠子關(guān)于紅珠對稱或不對稱有兩種情形：①對稱共有N2＝＝35種；②不對稱有N3＝N1－N2＝2968種，又同色珠

22、子換位后的相同的串法是重復的串法，因此關(guān)于紅球不對稱的串法有N4＝N3＝1484種，所以共有N＝N2＋N4＝1519種不同串法。 9．可重復排列，共有36＝729種報名方法。 習題解答 1．把兩次連續(xù)命中與一次命中的情形看成2個元素插入可知共有30種?；蛴酶F舉法把滿足條件的情形一一列舉出來 2．B．分組先分堆 3．先排1區(qū)，有4種方法，再排2區(qū)，有3種方法，如果3、5兩區(qū)同色，則4區(qū)有2種方法，否則4區(qū)只有一種方法。另外3、5兩區(qū)本身還有兩種選擇，故共有4×3×(1＋2)×2＝72種。 4．用“排除法”，從7個點中任取三點有C種取法，其中3個點在一直線上的有3個，故共有C－3＝32

23、個。 5．n個運動員兩兩配對有對，從中選出兩對共有C＝3C。 6．不防設b1

24、92種方法。故總計有108＋432＋192＝732種方法。 8．由a1a3，a3>a4，a4>a5可知，要么a2＝5，要么a4＝5（a1、a3、a5不可能是最大者），且a2≥3，a4≥3，a3≤3。①若a2＝5，則a4＝4或3。當a4＝4時，有3?。?種，當a4＝3時，有2！＝2種，這時共有6＋2＝8種；②同理當a4＝5時，也有8種，故共有16種。 9．前3位數(shù)是123的五位“漸升數(shù)”共有5＋4＋3＋2＋1＝15個數(shù)。同理，前3位數(shù)分別是124，125，126，127的五位“漸升數(shù)”分別有10，6，3，1個。即前兩位數(shù)是12的五位漸升數(shù)有35個

25、，類似可得前兩位數(shù)是13，14，15，16的五位“漸升數(shù)”分別有20個，10個，4個，1個。從而首位是1的五位“漸升數(shù)”共有35＋20＋10＋4＋1＝70個。同理，前兩位數(shù)是23的五位“漸升數(shù)”共有10＋6＋3＋1＝20個。前2位是24的五位“漸升數(shù)”共有6＋3＋1＝10個。所以第100個“漸升數(shù)”是24789。 10．先在第i盒里放入i個球（i＝1，2，…，10）這時共放了1＋2＋3＋…＋10＝55個球，還余下1941個球，轉(zhuǎn)化為把1941個球放入10個盒子中（有的盒中不放球），有C種放法。 11．分四種情形討論：1°有3 6種顏色，將一種顏色染下底，則上底有5種染法，按圓排列，其余4

26、個側(cè)面有3！種染法，共有5×3?。?0種；2°用5種顏色，選5種顏色有C種方法，再選一種染上下底，有5種，固定一種顏色朝東，朝西一面有3種選法，共有C×C×3 = 90種；3°用4種顏色，選4色，再選其中兩種各染一對對面有C×C＝90種。4°用3種色，選3色有C種，每種染相對兩面，染出的都是同一種，故共有C＝20種。故共有30＋90＋90＋20＝230種。 12．先把女性排定，有4！種方法，女性與女性之間若坐男性（包括這些女性的丈夫）必不少于兩個。同樣，在男性與男性之間坐著的女性也必不少于兩個，把座位連在一起的女性也必不少于兩個，把座位連在一起的女性視為一組，則4位女性的分組有4，3＋1，2

27、＋2，2＋1＋1，1＋1＋1＋1這5種，孤立坐著的女性必須在這一排座位的兩端，所以1＋1＋1＋1方案不合要求，女性分成2＋1＋1時，兩端必須坐著女性，這時男性只能分成2＋2，即女男男女女男男女，男性的排法只有1種，女性分種2＋2時，有4類： 女女男男男男女女 ， 女女男男男女女男 或 男女女男男男女女 ， 女女男男女女男男 或 男男女女男男女女 ， 男女女男男女女男，男性的排法分別有2，1，1，1種，女性分為3＋1時，有三類：女女女男男男男女或女男男男男女女女，男男女女女男男女或女男男男女女女男，男性的排法分別有2，1，1種，女性4人連排時，有三類，女女女女男男男男或男女女女女男男男，男男女女女女男男，男性的排法分別有3！，2！，2！種，于是排法總數(shù)為4?。?＋2＋2×1＋2×1＋1＋2×2＋2×1＋2×1＋2×3！＋2×2！×2?。?16種。 w。w-w*k&s%5￥u