排列組合問題的幾種基本方法

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

2、不等分；無序局部等分；無序局部等分；有序等分；有序等分；有序不等分；有序不等分；有序局部等分有序局部等分.處理問題的原則：處理問題的原則：1.分組（堆）問題分組（堆）問題例例1.有四項不同的工程，要發(fā)包給三個工程隊，要有四項不同的工程，要發(fā)包給三個工程隊，要求每個工程隊至少要得到一項工程求每個工程隊至少要得到一項工程. 共有多少種不同共有多少種不同的發(fā)包方式？的發(fā)包方式？解：解：要完成發(fā)包這件事，可以分為兩個步驟：要完成發(fā)包這件事，可以分為兩個步驟：先將四項工程分為三先將四項工程分為三“堆堆”，有，有211421226C C CA種分法；種分法；再將分好的三再將分好的三“堆堆”依次給三個工程隊

3、，依次給三個工程隊，有有3!6種給法種給法.共有共有6636種不同的發(fā)包方式種不同的發(fā)包方式.1.分組（堆）問題分組（堆）問題例例2 . 7人排成一排人排成一排.甲、乙兩人不相鄰，有多少甲、乙兩人不相鄰，有多少種不同的排法？種不同的排法？ 解：解：分兩步進(jìn)行：分兩步進(jìn)行：幾個元素不能相鄰幾個元素不能相鄰時時,先排一般元素，先排一般元素，再讓特殊元素插孔再讓特殊元素插孔.第第1步，把除甲乙外的一般人排列：步，把除甲乙外的一般人排列：55A有=120種排法第第2步，將甲乙分別插入到不同的間隙或兩端中步，將甲乙分別插入到不同的間隙或兩端中(插孔插孔)：26A有=30種插入法120 303600共有種

4、排法 解決一些不相鄰問題時，可以先排解決一些不相鄰問題時，可以先排“一一般般”元素然后插入元素然后插入“特殊特殊”元素，使問題得以元素，使問題得以解決解決.2.插空法：插空法：相鄰元素的排列，可以采用相鄰元素的排列，可以采用“局部到整體局部到整體”的的排法，即將相鄰的元素局部排列當(dāng)成排法，即將相鄰的元素局部排列當(dāng)成“一個一個”元素，元素，然后再進(jìn)行整體排列然后再進(jìn)行整體排列.3.捆綁法捆綁法例例3 . 6人排成一排人排成一排.甲、乙兩人必須相鄰甲、乙兩人必須相鄰,有多少有多少種不的排法種不的排法? 解：解：（1）分兩步進(jìn)行：分兩步進(jìn)行：甲甲 乙乙第一步，把甲乙排列第一步，把甲乙排列(捆綁捆綁)

5、：55A有120種排法第二步，甲乙兩個人的梱看作一個元素與其它的排隊：第二步，甲乙兩個人的梱看作一個元素與其它的排隊：22A有2種捆法2 120240共有種排法 幾個元素必須相鄰時幾個元素必須相鄰時,先先捆綁成一個元素，再與捆綁成一個元素，再與其它的進(jìn)行排列其它的進(jìn)行排列.例例4.5個人站成一排，甲總站在乙的右側(cè)的站法有個人站成一排，甲總站在乙的右側(cè)的站法有多少種？多少種？幾個元素幾個元素順序一定順序一定的排列問題，一般是先排列，再的排列問題，一般是先排列，再消去這幾個元素的順序消去這幾個元素的順序.或者，先讓其它元素選取位置或者，先讓其它元素選取位置排列，留下來的空位置自然就是順序一定的了排

6、列，留下來的空位置自然就是順序一定的了.4.消序法消序法(留空法留空法)解法解法1：將將5個人依次站成一排，有個人依次站成一排，有解法解法2：先讓甲乙之外的三人從先讓甲乙之外的三人從5個位置選出個位置選出3個站好，個站好，有有55A種站法，種站法，然后再消去甲乙之間的順序數(shù)然后再消去甲乙之間的順序數(shù)22A甲總站在乙的右側(cè)的有站法總數(shù)為甲總站在乙的右側(cè)的有站法總數(shù)為5355225 4 3AAA 35A種站法，留下的兩個位置自然給甲乙有種站法，留下的兩個位置自然給甲乙有1種站法種站法甲總站在乙的右側(cè)的有站法總數(shù)為甲總站在乙的右側(cè)的有站法總數(shù)為33551AA 變式：變式：如下圖所示如下圖所示,有有5

7、橫橫8豎構(gòu)成的方格圖豎構(gòu)成的方格圖,從從A到到B只能上行或右行只能上行或右行共有多少條不同的路線共有多少條不同的路線? 解解: 如圖所示如圖所示1234567將一條路經(jīng)抽象為如下的一個將一條路經(jīng)抽象為如下的一個排法排法(5-1)+(8-1)=11格格:其中必有四個其中必有四個和七個和七個組成組成!所以所以, 四個四個和七個和七個一個排序就對應(yīng)一條路經(jīng)一個排序就對應(yīng)一條路經(jīng),所以從所以從A到到B共有共有 5 14(5 1) (8 1)11CC條不同的路徑條不同的路徑. 4.消序法消序法(留空法留空法)也可以看作是也可以看作是1,2,3,4,5,6,7,順序一定的排列，順序一定的排列，有有種排法種

8、排法.11114747AAA n個個 相同小球放入相同小球放入m(mn)個盒子里個盒子里,要求每個盒子里要求每個盒子里至少有一個小球的放法等價于在至少有一個小球的放法等價于在n個相同小球之間形個相同小球之間形成的成的n-1個間隙里，用個間隙里，用m-1個隔板隔成個隔板隔成m組組.例例5. 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把把16個選手個選手名額分配到高三年級的名額分配到高三年級的1-4 個教學(xué)班個教學(xué)班,每班至少一個每班至少一個名額名額,則不同的分配方案共有則不同的分配方案共有_種種.5.剪截法（隔板法）：剪截法（隔板法）：解：解： 問題等價于把問題等價于把16個相同

9、小球放入個相同小球放入4個盒子里個盒子里,每個盒子至少有一個小球的放法種數(shù)問題每個盒子至少有一個小球的放法種數(shù)問題. 將將16個小球串成一串，截為個小球串成一串，截為4段有段有 315455C種截斷法，對應(yīng)放到種截斷法，對應(yīng)放到4個盒子里個盒子里.因此，不同的分配方案共有因此，不同的分配方案共有455種種 . n個個 相同小球放入相同小球放入m(mn)個盒子里個盒子里,要求每個盒子要求每個盒子里至少有一個小球的放法等價于里至少有一個小球的放法等價于n個相同小球串成一串個相同小球串成一串從小球之間間隙里選從小球之間間隙里選m-1個結(jié)點(diǎn)剪截成個結(jié)點(diǎn)剪截成m段段.變式：變式： 某校準(zhǔn)備參加今年高中數(shù)

10、學(xué)聯(lián)賽某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把把16個選個選手名額分配到高三年級的手名額分配到高三年級的1-4 個教學(xué)班個教學(xué)班,每班的名額每班的名額不少于該班的序號數(shù)不少于該班的序號數(shù),則不同的分配方案共有則不同的分配方案共有_種種.5.剪截法（隔板法）剪截法（隔板法） ：解：解： 問題等價于先給問題等價于先給2班班1個，個，3班班2個，個，4班班3個，個，再把余下的再把余下的10個相同小球放入個相同小球放入4個盒子里個盒子里,每個盒子每個盒子至少有一個小球的放法種數(shù)問題至少有一個小球的放法種數(shù)問題. 將將10個小球串成一串，截為個小球串成一串，截為4段有段有 3984C 種截斷法，對應(yīng)放到種截斷法

11、，對應(yīng)放到4個盒子里個盒子里.因此，不同的分配方案共有因此，不同的分配方案共有84種種 .編號為編號為1至至n的的n個小球放入編號為個小球放入編號為1到到 n的的n個盒個盒子里子里,每個盒子放一個小球每個盒子放一個小球.要求小球與盒子的編要求小球與盒子的編號都不同號都不同,這種排列稱為這種排列稱為錯位排列錯位排列.6.錯位法：錯位法：特別當(dāng)特別當(dāng)n=2,3,4,5時的錯位數(shù)各為時的錯位數(shù)各為1,2,9,44.例例6. 編號為編號為1至至6的的6個小球放入編號為個小球放入編號為1至至6的的6個個盒子里盒子里,每個盒子放一個小球每個盒子放一個小球,其中恰有其中恰有2個小球與盒個小球與盒子的編號相同

12、的放法有子的編號相同的放法有_種種.解：解： 選取編號相同的兩組球和盒子的方法有選取編號相同的兩組球和盒子的方法有 2615C 種種,其余其余4組球與盒子需錯位排列有組球與盒子需錯位排列有9種放法種放法.故所求方法有故所求方法有159135種種.7.剔除法剔除法 從總體中排除不符合條件的方法數(shù)，這是一從總體中排除不符合條件的方法數(shù)，這是一種間接解題的方法種間接解題的方法. 例例7. 從集合從集合0,1,2,3,5,7,11中任取中任取3個元素分別作為直個元素分別作為直線方程線方程Ax+By+C=0中的中的A、B、C，所得的經(jīng)過坐標(biāo)，所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有原點(diǎn)的直線有_條條.解：所有這樣的直

13、線共有解：所有這樣的直線共有 條，條，其中不過原點(diǎn)的直線有其中不過原點(diǎn)的直線有 條，條，37210A 所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有210-18030條條.1266180AA 排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這類應(yīng)用題時，要注意使用相關(guān)知識對答案進(jìn)行取舍類應(yīng)用題時，要注意使用相關(guān)知識對答案進(jìn)行取舍.B B 鞏固練習(xí)鞏固練習(xí)A 4. 5個人排成一排，其中甲、乙不相鄰的排法種數(shù)是個人排成一排，其中甲、乙不相鄰的排法種數(shù)是（）（）A.6B.12C.72D.144C鞏固練習(xí)鞏固練習(xí)排列、組合問