1、2022/9/151第一章 排列、組合和二項(xiàng)定理15 九月 2022解排列組合問題的幾種基本方法從n個(gè)不同元素中,任取m個(gè)元素,按照一定的順序排成一列,叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列.2.組合的定義:從n個(gè)不同元素中,任取m個(gè)元素,并成一組,叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合.3.排列數(shù)公式:4.組合數(shù)公式:1.排列的定義:排列與組合的區(qū)別與聯(lián)系:與順序有關(guān)的為排列問題,與順序無關(guān)的為組合問題.2022/9/153要明確組的順序時(shí)，必須先分組后再把組數(shù)當(dāng)作元素個(gè)數(shù)作全排列.若干個(gè)不同的元素局部“等分”有 個(gè)均等組,要將選取出每一個(gè)組的組合數(shù)的乘積除以m! 若干個(gè)不同的元素“

2、等分”為 個(gè)組,要將選取出每一個(gè)堆的組合數(shù)的乘積除以m! 非均分組問題，只要按比例取出分完再用乘法原理作積. 分組問題的六個(gè)模型：無序不等分；無序等分；無序局部等分；(有序不等分；有序等分；有序局部等分.)處理問題的原則：1.分組問題2022/9/154例1.有四項(xiàng)不同的工程，要分包給三個(gè)工程隊(duì)，要求每個(gè)工程隊(duì)至少要得到一項(xiàng)工程. 共有多少種不同的發(fā)包方式？解：要完成發(fā)包這件事，可以分為兩個(gè)步驟：先將四項(xiàng)工程分為三“組”，有種分法；再將分好的三“組”依次給三個(gè)工程隊(duì)，有3!6種給法.共有6636種不同的發(fā)包方式.1.分組問題2022/9/156相鄰元素的排列，可以采用“局部到整體”的排法，即將

3、相鄰的元素局部排列當(dāng)成“一個(gè)”元素，然后再進(jìn)行整體排列.3.捆綁法例3 . 6人排成一排.甲、乙兩人必須相鄰,有多少種不的排法? 解：（1）分兩步進(jìn)行：甲 乙第一步，把甲乙排列(捆綁)：第二步，甲乙兩個(gè)人的梱看作一個(gè)元素與其它的排隊(duì)： 幾個(gè)元素必須相鄰時(shí),先捆綁成一個(gè)元素，再與其它的進(jìn)行排列.2022/9/157例4.5個(gè)人站成一排，甲總站在乙的右側(cè)的有多少種站法？幾個(gè)元素順序一定的排列問題，一般是先排列，再消去這幾個(gè)元素的順序.或者，先讓其它元素選取位置排列，留下來的空位置自然就是順序一定的了.4.消序法(留空法)解法1：將5個(gè)人依次站成一排，有解法2：先讓甲乙之外的三人從5個(gè)位置選出3個(gè)站

4、好，有種站法，然后再消去甲乙之間的順序數(shù)甲總站在乙的右側(cè)的有站法總數(shù)為種站法，留下的兩個(gè)位置自然給甲乙有1種站法甲總站在乙的右側(cè)的有站法總數(shù)為2022/9/159 n個(gè) 相同小球放入m(mn)個(gè)盒子里,要求每個(gè)盒子里至少有一個(gè)小球的放法等價(jià)于n個(gè)相同小球串成一串從間隙里選m-1個(gè)結(jié)點(diǎn)剪截成m段.例5. 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個(gè)選手名額分配到高三年級(jí)的4 個(gè)教學(xué)班,每班至少一個(gè)名額,則不同的分配方案共有_種.5.剪截法（隔板法）：解： 問題等價(jià)于把16個(gè)相同小球放入4個(gè)盒子里,每個(gè)盒子至少有一個(gè)小球的放法種數(shù)問題. 將16個(gè)小球串成一串，截為4段有 種截?cái)喾?，?duì)應(yīng)放到4個(gè)盒子里.因

5、此，不同的分配方案共有455種 .2022/9/1510 n個(gè) 相同小球放入m(mn)個(gè)盒子里,要求每個(gè)盒子里至少有一個(gè)小球的放法等價(jià)于n個(gè)相同小球串成一串從間隙里選m-1個(gè)結(jié)點(diǎn)剪截成m段.變式： 某校準(zhǔn)備參加今年高中數(shù)學(xué)聯(lián)賽,把16個(gè)選手名額分配到高三年級(jí)的1到4 班4個(gè)教學(xué)班,每班的名額不少于該班的序號(hào)數(shù),則不同的分配方案共有_種.5.剪截法：解： 問題等價(jià)于先給2班1個(gè)，3班2個(gè)，4班3個(gè)，再把余下的10個(gè)相同小球放入4個(gè)盒子里,每個(gè)盒子至少有一個(gè)小球的放法種數(shù)問題. 將10個(gè)小球串成一串，截為4段有 種截?cái)喾?，?duì)應(yīng)放到4個(gè)盒子里.因此，不同的分配方案共有84種 .2022/9/1511

6、編號(hào)為1至n的n個(gè)小球放入編號(hào)為1到 n的n個(gè)盒子里,每個(gè)盒子放一個(gè)小球.要求小球與盒子的編號(hào)都不同,這種排列稱為錯(cuò)位排列.6.錯(cuò)位法：特別當(dāng)n=2,3,4,5時(shí)的錯(cuò)位數(shù)各為1,2,9,44.例6. 編號(hào)為1至6的6個(gè)小球放入編號(hào)為1至6的6個(gè)盒子里,每個(gè)盒子放一個(gè)小球,其中恰有2個(gè)小球與盒子的編號(hào)相同的放法有_種.解： 選取編號(hào)相同的兩組球和盒子的方法有 種,其余4組球與盒子需錯(cuò)位排列有9種放法.故所求方法有159135種.2022/9/15127.剔除法 從總體中排除不符合條件的方法數(shù)，這是一種間接解題的方法. 例7. 從集合0,1,2,3,5,7,11中任取3個(gè)元素分別作為直線方程Ax+

7、By+C=0中的A、B、C，所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有_條.解：所有這樣的直線共有 條，其中不過原點(diǎn)的直線有 條，所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有210-18030條. 排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識(shí)聯(lián)系，從而增加了問題的綜合性，解答這類應(yīng)用題時(shí)，要注意使用相關(guān)知識(shí)對(duì)答案進(jìn)行取舍.一、等分組與不等分組問題例、6本不同的書，按下列條件，各有多少種不同的分法；（1）分給甲、乙、丙三人，每人兩本；90（2）分成三份，每份兩本；15（3）分成三份，一份1本，一份2本，一份3本；60（4）分給甲、乙、丙3人，一人1本，一人2本，一人3本；360（5）分給甲、乙、丙3人，每人至少一本；540（6）分給5個(gè)人，每人至少一本；1800（7）6本相同的書，分給甲乙丙三人，每人至少一本。10例8、8雙互不相同的鞋子混裝在一只口袋中，從中任意取出4只，試求滿足如下條件各有多少種情況：（1）4只鞋子恰有兩雙；（2） 4只鞋子沒有成雙的；（3） 4只鞋子只有一雙。2022/9/1516A