高中數(shù)學(xué)排列組合-組合(2)

1、2021/3/101 1.2.2 1.2.2 組合組合(2)(2) 2021/3/102 要明確堆的順序時(shí)，必須先分堆后再把堆數(shù)當(dāng)要明確堆的順序時(shí)，必須先分堆后再把堆數(shù)當(dāng) 作元素個(gè)數(shù)作全排列作元素個(gè)數(shù)作全排列. 若干個(gè)不同的元素局部若干個(gè)不同的元素局部“等分等分”有有 個(gè)均等個(gè)均等 堆堆,要將選取出每一個(gè)堆的組合數(shù)的乘積除以要將選取出每一個(gè)堆的組合數(shù)的乘積除以m! 若干個(gè)不同的元素若干個(gè)不同的元素“等分等分”為為 個(gè)堆個(gè)堆,要將要將 選取出每一個(gè)堆的組合數(shù)的乘積除以選取出每一個(gè)堆的組合數(shù)的乘積除以m! 非均分堆問題，只要按比例取出分完再用乘非均分堆問題，只要按比例取出分完再用乘 法原理作積法原

2、理作積. 分組（堆）問題的六個(gè)模型：分組（堆）問題的六個(gè)模型：無序不等分；無序不等分； 無序等分；無序等分；無序局部等分；無序局部等分；(有序不等分；有序不等分； 有序等分；有序等分；有序局部等分有序局部等分.) 處理問題的原則：處理問題的原則： 1.分組（堆）問題分組（堆）問題 2021/3/103 例例1.有四項(xiàng)不同的工程，要發(fā)包給三個(gè)工程隊(duì)，要有四項(xiàng)不同的工程，要發(fā)包給三個(gè)工程隊(duì)，要 求每個(gè)工程隊(duì)至少要得到一項(xiàng)工程求每個(gè)工程隊(duì)至少要得到一項(xiàng)工程. 共有多少種不同共有多少種不同 的發(fā)包方式？的發(fā)包方式？ 解：解：要完成發(fā)包這件事，可以分為兩個(gè)步驟：要完成發(fā)包這件事，可以分為兩個(gè)步驟： 先將

3、四項(xiàng)工程分為三先將四項(xiàng)工程分為三“堆堆”，有，有 211 421 2 2 6 C C C A 種分法；種分法； 再將分好的三再將分好的三“堆堆”依次給三個(gè)工程隊(duì)，依次給三個(gè)工程隊(duì)， 有有3!6種給法種給法. 共有共有6636種不同的發(fā)包方式種不同的發(fā)包方式. 1.分組（堆）問題分組（堆）問題 2021/3/104 例例2 . 7人排成一排人排成一排.甲、乙兩人不相鄰，有多少種不同的排法？甲、乙兩人不相鄰，有多少種不同的排法？ 解：解：分兩步進(jìn)行：分兩步進(jìn)行： 幾個(gè)元素不能相鄰幾個(gè)元素不能相鄰 時(shí)時(shí),先排一般元素，先排一般元素， 再讓特殊元素插孔再讓特殊元素插孔. 第第1步，把除甲乙外的一般人排

4、列：步，把除甲乙外的一般人排列： 5 5 A有=120種排法 第第2步，將甲乙分別插入到不同的間隙或兩端中步，將甲乙分別插入到不同的間隙或兩端中(插孔插孔)： 2 6 A有=30種插入法 120 303600共有種排法 解決一些不相鄰問題時(shí)，可以先排解決一些不相鄰問題時(shí)，可以先排“一一 般般”元素然后插入元素然后插入“特殊特殊”元素，使問題得以元素，使問題得以 解決解決. 2.插空法：插空法： 2021/3/105 相鄰元素的排列，可以采用相鄰元素的排列，可以采用“局部到整體局部到整體”的的 排法，即將相鄰的元素局部排列當(dāng)成排法，即將相鄰的元素局部排列當(dāng)成“一個(gè)一個(gè)”元素，元素， 然后再進(jìn)行整

5、體排列然后再進(jìn)行整體排列. 3.捆綁法捆綁法 例例3 . 6人排成一排人排成一排.甲、乙兩人必須相鄰甲、乙兩人必須相鄰,有多少種不的排法有多少種不的排法? 解：解：（1）分兩步進(jìn)行：分兩步進(jìn)行： 甲甲 乙乙 第一步，把甲乙排列第一步，把甲乙排列(捆綁捆綁)： 5 5 A有120種排法 第二步，甲乙兩個(gè)人的梱看作一個(gè)元素與其它的排隊(duì)：第二步，甲乙兩個(gè)人的梱看作一個(gè)元素與其它的排隊(duì)： 2 2 A有2種捆法 2 120240共有種排法 幾個(gè)元素必須相鄰時(shí)幾個(gè)元素必須相鄰時(shí),先先 捆綁成一個(gè)元素，再與捆綁成一個(gè)元素，再與 其它的進(jìn)行排列其它的進(jìn)行排列. 2021/3/106 例例4.5個(gè)人站成一排，甲

6、總站在乙的右側(cè)的有多少個(gè)人站成一排，甲總站在乙的右側(cè)的有多少 種站法？種站法？ 幾個(gè)元素幾個(gè)元素順序一定順序一定的排列問題，一般是先排列，再的排列問題，一般是先排列，再 消去這幾個(gè)元素的順序消去這幾個(gè)元素的順序.或者，先讓其它元素選取位置或者，先讓其它元素選取位置 排列，留下來的空位置自然就是順序一定的了排列，留下來的空位置自然就是順序一定的了. 4.消序法消序法(留空法留空法) 解法解法1：將將5個(gè)人依次站成一排，有個(gè)人依次站成一排，有 解法解法2：先讓甲乙之外的三人從先讓甲乙之外的三人從5個(gè)位置選出個(gè)位置選出3個(gè)站好，個(gè)站好， 有有 5 5 A 種站法，種站法， 然后再消去甲乙之間的順序數(shù)

7、然后再消去甲乙之間的順序數(shù) 2 2 A 甲總站在乙的右側(cè)的有站法總數(shù)為甲總站在乙的右側(cè)的有站法總數(shù)為 5 3 5 5 2 2 5 4 3 A A A 3 5 A 種站法，留下的兩個(gè)位置自然給甲乙有種站法，留下的兩個(gè)位置自然給甲乙有1種站法種站法 甲總站在乙的右側(cè)的有站法總數(shù)為甲總站在乙的右側(cè)的有站法總數(shù)為 33 55 1AA 2021/3/107 變式：變式：如下圖所示如下圖所示,有有5 橫橫8豎構(gòu)成的方格圖豎構(gòu)成的方格圖,從從 A到到B只能上行或右行只能上行或右行 共有多少條不同的路線共有多少條不同的路線? 解解: 如圖所示如圖所示 1 2 3 4 5 6 7 將一條路經(jīng)抽象為如下的一個(gè)將一

8、條路經(jīng)抽象為如下的一個(gè) 排法排法(5-1)+(8-1)=11格格: 其中必有四個(gè)其中必有四個(gè)和七個(gè)和七個(gè)組成組成! 所以所以, 四個(gè)四個(gè)和七個(gè)和七個(gè)一個(gè)排序就對應(yīng)一條路經(jīng)一個(gè)排序就對應(yīng)一條路經(jīng), 所以從所以從A到到B共有共有 5 14 (5 1) (8 1)11 CC 條不同的路徑條不同的路徑. 4.消序法消序法(留空法留空法) 也可以看作是也可以看作是 1,2,3,4,5,6,7, 順序一定的排列，順序一定的排列， 有有 種排法種排法. 11 11 47 47 A AA 2021/3/108 n個(gè)個(gè) 相同小球放入相同小球放入m(mn)個(gè)盒子里個(gè)盒子里,要求每個(gè)要求每個(gè) 盒子里至少有一個(gè)小球的

9、放法等價(jià)于盒子里至少有一個(gè)小球的放法等價(jià)于n個(gè)相同小球個(gè)相同小球 串成一串從間隙里選串成一串從間隙里選m-1個(gè)結(jié)點(diǎn)剪截成個(gè)結(jié)點(diǎn)剪截成m段段. 例例5. 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把把16個(gè)選手個(gè)選手 名額分配到高三年級的名額分配到高三年級的1-4 個(gè)教學(xué)班個(gè)教學(xué)班,每班至少一個(gè)每班至少一個(gè) 名額名額,則不同的分配方案共有則不同的分配方案共有_種種. 5.剪截法（隔板法）：剪截法（隔板法）： 解：解： 問題等價(jià)于把問題等價(jià)于把16個(gè)相同小球放入個(gè)相同小球放入4個(gè)盒子里個(gè)盒子里, 每個(gè)盒子至少有一個(gè)小球的放法種數(shù)問題每個(gè)盒子至少有一個(gè)小球的放法種數(shù)問題. 將將16個(gè)

10、小球串成一串，截為個(gè)小球串成一串，截為4段有段有 3 15 455C 種截?cái)喾?，對?yīng)放到種截?cái)喾ǎ瑢?yīng)放到4個(gè)盒子里個(gè)盒子里. 因此，不同的分配方案共有因此，不同的分配方案共有455種種 . 2021/3/109 n個(gè)個(gè) 相同小球放入相同小球放入m(mn)個(gè)盒子里個(gè)盒子里,要求每個(gè)要求每個(gè) 盒子里至少有一個(gè)小球的放法等價(jià)于盒子里至少有一個(gè)小球的放法等價(jià)于n個(gè)相同小球個(gè)相同小球 串成一串從間隙里選串成一串從間隙里選m-1個(gè)結(jié)點(diǎn)剪截成個(gè)結(jié)點(diǎn)剪截成m段段. 變式：變式： 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把把16個(gè)選個(gè)選 手名額分配到高三年級的手名額分配到高三年級的1-4 個(gè)

11、教學(xué)班個(gè)教學(xué)班,每班的名額每班的名額 不少于該班的序號數(shù)不少于該班的序號數(shù),則不同的分配方案共有則不同的分配方案共有_種種. 5.剪截法：剪截法： 解：解： 問題等價(jià)于先給問題等價(jià)于先給2班班1個(gè)，個(gè)，3班班2個(gè)，個(gè)，4班班3個(gè)，個(gè)， 再把余下的再把余下的10個(gè)相同小球放入個(gè)相同小球放入4個(gè)盒子里個(gè)盒子里,每個(gè)盒子每個(gè)盒子 至少有一個(gè)小球的放法種數(shù)問題至少有一個(gè)小球的放法種數(shù)問題. 將將10個(gè)小球串成一串，截為個(gè)小球串成一串，截為4段有段有 3 9 84C 種截?cái)喾?，對?yīng)放到種截?cái)喾?，對?yīng)放到4個(gè)盒子里個(gè)盒子里. 因此，不同的分配方案共有因此，不同的分配方案共有84種種 . 2021/3/10

12、10 7.剔除法剔除法 從總體中排除不符合條件的方法數(shù)，這是一從總體中排除不符合條件的方法數(shù)，這是一 種間接解題的方法種間接解題的方法. 例例7. 從集合從集合0,1,2,3,5,7,11中任取中任取3個(gè)元素分別作為直個(gè)元素分別作為直 線方程線方程Ax+By+C=0中的中的A、B、C，所得的經(jīng)過坐標(biāo)，所得的經(jīng)過坐標(biāo) 原點(diǎn)的直線有原點(diǎn)的直線有_條條. 解：所有這樣的直線共有解：所有這樣的直線共有 條，條， 其中不過原點(diǎn)的直線有其中不過原點(diǎn)的直線有 條，條， 3 7 210A 所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有210-18030條條. 12 66 180AA 排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解 析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這 類應(yīng)用題時(shí)，要注意使用相關(guān)知識對答案進(jìn)行取舍類應(yīng)用題時(shí)，要注意使用相關(guān)知識對答案進(jìn)行取舍. 2021/3/1011 B B 鞏固練習(xí)鞏固練習(xí) 2021/3/1012 A 4. 5個(gè)人排成一排，其中甲、乙不相鄰的排法種數(shù)是個(gè)人排成一排，其中甲、乙不相鄰的排法種數(shù)是 （）（） A.6B.12C.72D.144 C 鞏固