排列組合典型問題選講

1、一.集團(tuán)排列問題：部分元素必須安排在一起（相鄰）的排列問題，稱之為“集團(tuán)排列”問題.解決這類問題，常用“捆綁法”，其方法是先排“集團(tuán)”內(nèi)部的元素，再把這個(gè)大“元素”與其它元素一起排列即可.例1若7位同學(xué)站成一排（1）甲、乙兩同學(xué)必須相鄰的排法共有多少種？（2）甲、乙和丙三個(gè)同學(xué)都相鄰的排法共有多少種？（3）甲、乙兩同學(xué)必須相鄰，而且丙不能站在排頭和排尾的排法有多少種？（4）甲、乙、丙三個(gè)同學(xué)必須站在一起，另外四個(gè)人也必須站在一起的排法有多少種？解：（1）先將甲、乙兩位同學(xué)“捆綁”在一起看成一個(gè)元素與其余的5個(gè)元素（同學(xué)）一起進(jìn)行全排列有A6種方法；再將甲、乙兩個(gè)同學(xué)“松綁”進(jìn)行排列有A；種方法

2、.所以這樣的排法一共有A 6=1440種.（2）方法同上，一共有 A5 A =720種.（3）解法一：將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素，此時(shí)一共有6個(gè)元素，因?yàn)楸荒苷驹谂蓬^和排尾，所以可以從其余的 5個(gè)元素中選取2個(gè)元素放在排頭和排尾，有 A2種方法；將剩下的4個(gè)元素進(jìn) 行全排列有 A：種方法；最后將甲、乙兩個(gè)同學(xué)“松綁”進(jìn)行排列有A；種方法.所以這樣的排法一共有-2 - 4 - 2.、.A5 A4 A2 =960 種方法.解法二：將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素，此時(shí)一共有6個(gè)元素，若丙站在排頭或排尾有_5.,_6_5、_22A5種方法，所以，丙不能站在排頭和排尾的排法有（

3、A6 -2A5） A； =960種方法.解法三：將甲、乙兩同學(xué)“捆綁”在一起看成一個(gè)元素，此時(shí)一共有6個(gè)元素，因?yàn)楸荒苷驹谂蓬^和排尾，所以可以從其余的四個(gè)位置選擇共有A：種方法，再將其余的5個(gè)元素進(jìn)行全排列共有 A5種方法，最后將甲、乙兩同學(xué)“松綁”，所以，這樣的排法一共有 A4 A55 A： =960種方法.（4）將甲、乙、丙三個(gè)同學(xué)“捆綁”在一起看成一個(gè)元素，另外四個(gè)人“捆綁”在一起看成一個(gè)元素， 時(shí)一共有2個(gè)元素，一共有排法種數(shù)：A3A4A2 =288 （種）說明：對(duì)于相鄰問題，常用“捆綁法”（先捆后松）.二.間隔排列問題：部分元素不能安排在一起（間隔）的排列問題，稱之為“間隔排列”問

4、題.解決這類問題，常用“插空法”，其方法是先排不需要間隔的元素，再將需要間隔的元素通過插空的方式插進(jìn)來即可.例2在一條南北方向的步行街同側(cè)有8塊廣告牌，牌的底色可選用紅、藍(lán)兩種顏色.若只要求相鄰兩塊牌的底色不都為紅色，則不同的配色方案共有（）A.55.B.56.C.46.D.45.解：沒有紅牌，一種方法；有一塊紅牌，讓其插空，有c；種方法；有二塊紅牌，讓其插空，有c。種方法； 有三塊紅牌，讓其插空，有c；種方法；有四塊紅牌，讓其插空，有c54種方法；共有方法 1+C； +Cy +C；+C； =55 種.說明：對(duì)于不相鄰問題，常用“插空法”（特殊元素后考慮）例3某儀表顯示屏上一排有 7個(gè)小孔，每

5、個(gè)小孔可顯示出 0或1,若每次顯示其中三個(gè)孔，但相鄰的兩 孔不能同時(shí)顯示，則這顯示屏可以顯示的不同信號(hào)的種數(shù)有 種.解：四個(gè)孔不亮，三個(gè)孔亮，相當(dāng)于三個(gè)亮著的孔在四個(gè)不亮的孔之間插空，故有c53 M 2 M 2 M 2 =80 種方法.三.部分不同元素定序與部分相同元素排列問題：部分不同元素在排列前后的順序固定不變（不一定相鄰）的排列問題，稱之為“定序排列”問題.解決這類問題的基本方法有三種（1） “消序法”（有些地方叫“整體法”），即若有m+n個(gè)元素排成一列，其中有 m個(gè)元素之間的排列順序不變，將這 m + n個(gè)元素任意排成一列，共有Am：種不同的排法，其中未定序的n個(gè)元素排在某一特定位置的

6、排列的個(gè)數(shù)有 Am種排法，但只有一個(gè)排列是我們所需要的排列，因而共有m：un包0種不同的排法.類似地還可推廣到一般情形，如有有 m+n+k個(gè)元素排成一列，其中有 m個(gè)元素之間的排列順序不變，且另外 k個(gè)元m，n k素之間的排列順序也不變，則共有牛擊中不同的算法.m Akmm k（2）逐一插空法：先將定序的元素進(jìn)行排列，再將其它元素逐一插入這組元素兩端及中間（3）優(yōu)序法：先將所有位置中按 “特殊元素”個(gè)數(shù)選出若干位置,并把這些特殊元素按規(guī)定順序排上去,再將普通元素在其余位置上全排列例4若5男5女排成一排，按下列要求各有多少種排法（1）男女相間；（2）女生按指定順序排列.解：（1）先將男生排好，有

7、2種排法；再將5名女生插在男生之間的 6個(gè)“空擋”（包括兩端）中，有2A5種排法.故本題的排法有 N =2A5 A5 =28800 （種）；A10 .(2)方法 1 (消序法)：N =Af = A50 =30240； A方法2 （逐一插空法）：5個(gè)女生按序排列，有 1中方法，5個(gè)男生逐個(gè)才1空，有 6,7,8,9,10 種方法，共 有 6 M 7 M8 M 9父 10 = 30240 種方法.方法3 （優(yōu)序法）：設(shè)想有10個(gè)位置，先將男生排在其中的任意5個(gè)位置上，有 A50種排法；余下的5個(gè)位置排女生，因?yàn)榕捻樞蛞呀?jīng)指定，所以她們只有一種排法故本題的結(jié)論為 N = A0父1 =30240

8、（種）.例5今有2本相同的語(yǔ)文書，3本相同的數(shù)學(xué)書，4本相同的英語(yǔ)書排成一排，有多少種不同的排法？a9解：（消序法）有 2A3 4 =1260種.A2A3A4例6 一個(gè)樓梯共18個(gè)臺(tái)階，12步登完，可一步登一個(gè)臺(tái)階，也可一步登兩個(gè)臺(tái)階，一共有多少種不同的走法？解：根據(jù)題意，要想12步登完，只能6個(gè)一步登一個(gè)臺(tái)階，6個(gè)一步登二個(gè)臺(tái)階.因此，把問題轉(zhuǎn)化為“相 同元素”的排列問題.因此有一A4 =924 （種）A6A6點(diǎn)評(píng)：對(duì)于部分不同元素定序排列以及相同元素的排列問題，可用優(yōu)序法【隨堂練習(xí)】1 .從5位同學(xué)中選派4位同學(xué)在星期五、星期六、星期日參加公益活動(dòng)，每人一天，要求星期五有2人參加，星期六、

9、星期日各有1人參加，則不同的選派方法共有（ B ）A. 40 種B.60種C. 100 種D. 120 種2 .安排3名支教老師去6所學(xué)校任教，每校至多 2人，則不同的分配方案共有 210種.（用數(shù)字作答）3 .用數(shù)字0, 1, 2, 3, 4, 5組成沒有重復(fù)數(shù)字，且比20000大的五位偶數(shù)有（A.288 個(gè) B.240 個(gè) C.144 個(gè) D.1264 .如圖，用6種不同的顏色給圖中的 4個(gè)格子涂色，每個(gè)格子涂一種顏色，要求最多使用3種顏色且相鄰的兩個(gè)格子顏色不同，則不同的涂色方法共有390種（用數(shù)字作答）5 .某校開設(shè)9門課程供學(xué)生選修，其中 A,B,C三門由于上課時(shí)間相同，至多選一門，

10、學(xué)校規(guī)定每位同學(xué)選修4門，共有 75種不同選修方案.（用數(shù)值作答）6 .從班委會(huì)5名成員中選出3名，分別擔(dān)任班級(jí)學(xué)習(xí)委員、文娛委員與體育委員，其中甲、乙二人不能擔(dān)任文娛委員，則不同的選法共有36種.（用數(shù)字作答）【課后作業(yè)】1 .某校安排5個(gè)班到4個(gè)工廠進(jìn)行社會(huì)實(shí)踐，每個(gè)班去一個(gè)工廠，每個(gè)工廠至少安排一個(gè)班，不同的安排方法共有240種.（用數(shù)字作答）2 .將數(shù)字 1,2, 3, 4, 5, 6拼成一列，記第 i 個(gè)數(shù)為 a (i=1, 2,，6),若 &#1, %#3, a5#5, a1 <a3 <% ,則不同的排列方法有 30 種（用數(shù)字作答）解：分兩步：（1）先排a1,

11、 a3, a5,當(dāng)a1 =2時(shí)，有2種；當(dāng)a1 =3時(shí)，有2種；當(dāng)& =4時(shí)，有1種,共有5種；（2）再排a2,%，%,共有 A =6種，故不同的排列方法種數(shù)為 5X6=30,填30.3 .中韓兩支圍棋隊(duì)各由 8人組成，按事先排好的次序出場(chǎng)進(jìn)行圍棋擂臺(tái)賽，雙方先由 1號(hào)隊(duì)員比賽，負(fù)者被淘汰，勝者再與負(fù)方2號(hào)隊(duì)員比賽，直到有一方全部被淘汰為止，另一方獲勝，形成一個(gè)比賽過程.（1）已知中方動(dòng)用了 5名隊(duì)員，取得了勝利，問這樣的比賽過程有多少種？（2）求由中方第8位選手獲得最后勝利的概率 .解：（1）中方勝利時(shí)，雙方共有 8 + 5 = 13名隊(duì)員參加了比賽，將他們按淘汰的順序從左向右排列，

12、則最右為中方5號(hào)，右第二個(gè)為韓方 8號(hào)，從右第三個(gè)至最左，共 11個(gè)位置上，有4個(gè)位置排中方隊(duì)員，其余排韓方隊(duì)員，每一種排法，對(duì)應(yīng)一種比賽結(jié)果，故共有C： =330種.(2)PC86 154 .若7位同學(xué)站成一排（1）甲、乙兩同學(xué)不能相鄰的排法共有多少種？（2）甲、乙和丙三個(gè)同學(xué)都不能相鄰的排法共有多少種?解：（1）解法一：（排除法）A； A6八；=3600；解法二：（插空法）先將其余五個(gè)同學(xué)排好有A5種方法，此時(shí)他們留下六個(gè)位置（就稱為“空”吧），再將甲、乙同學(xué)分別插入這六個(gè)位置（空）有A2種方法，所以一共有 A：A2 =3600種方法.（2）先將其余四個(gè)同學(xué)排好有A4種方法，此時(shí)他們留下五

13、個(gè)“空”，再將甲、乙和丙三個(gè)同學(xué)分別插入這五個(gè)“空”有 A；種方法，所以一共有 A4 A3 = 1440種.【課后記】四.錯(cuò)位排列問題n個(gè)不同元素排成一排，有 m個(gè)元素（mWn）不排在相應(yīng)位置的排列種數(shù)共有:An C1 An 4' !：；'C2An-2 -C3 An -3 . （ 1）mCmAn mAn CmAn 4 CmAn -2 CmAn -3（ 1） CmAn 用.當(dāng)n = m時(shí)，規(guī)定A0 =0! =1 ,這個(gè)公式亦成立.例7五封標(biāo)號(hào)為15的信放進(jìn)5個(gè)編號(hào)為15的信箋里面，若信的編號(hào)與信箋的編號(hào)都不相同，一共有多少種不同放法.解：這是著名的信封問題，很多著名數(shù)學(xué)家都研究過

14、.瑞士數(shù)學(xué)家歐拉按一般情況給出了一個(gè)遞推公式：用A、B、C表示寫著n位友人名字的信封，a、b、c表示n份相應(yīng)的寫好的信.把錯(cuò)裝的總數(shù)記為f(n).假設(shè)把a(bǔ)錯(cuò)裝進(jìn)B里了，包含著這個(gè)錯(cuò)誤的一切錯(cuò)裝法分兩類：(1) b錯(cuò)裝進(jìn)A里，這時(shí)每種錯(cuò)裝的其余部分都與a、b、A、B無關(guān)，應(yīng)有f(n-2)種錯(cuò)裝法.(2) b錯(cuò)裝進(jìn)A、B之外的信封，這時(shí)的裝信工作實(shí)際是把(除a之外的)信紙b、c裝入(除B之外的)n_1個(gè)信封A、C，顯然這種錯(cuò)裝方法有f(n1)種.錯(cuò)裝的其余部分都與 a、b、A、B無關(guān)，應(yīng)有f(n-2)種錯(cuò)裝法.總之在a錯(cuò)裝入B的錯(cuò)誤之下，共有錯(cuò)裝法f (n-1)+f(n-2)種.裝入D的n2種錯(cuò)誤

15、之下，同樣都有f (n1)十f(n2)種錯(cuò)裝法.因此 f(n) =(n -1)f (n 1) + f (n 2),顯然 f (1) = 0 , f (2) =1.由此可得f (5) -44.注意：用容斥原理亦可解決此題.111c 1W遍結(jié)論為專日排公式 1： f(n)=n!1 + + ,+(1).1! 2! 3!n!錯(cuò)排遞推公式 2：f(n)=(n-1)f (n-1)+ f(n-2)錯(cuò)排公式3: A ©An： CmAnnj -CmAnn - (-1)mC：An；m例8有5個(gè)人站成一排，其中 A不站第一位，B不站第二位，C不站第三位，D不站第四位，E不站第五位，共有多少種不同的站法.解

16、析：上面兩例實(shí)際上可以看成n個(gè)不同元素中有 m (mWn)錯(cuò)位排列的問題.而這個(gè)問題是其特殊情況，即全錯(cuò)位排列問題共有 A5 -C5A4 +CIA33 -C3A22 +C54A1 -C；A0=44種(注意 A0=0!=1)例9同室四人各寫一張賀年卡，先集中起來.然后每人從中拿一張別人送出的賀年卡.則四張賀年卡不同的分配方式有A.6 種B.9 種C.11 種D.23 種解析：由上面公式得:a4 c4A +c：8 -c43A1 +c4a0 =9種，選擇 b答案.因此可得到全錯(cuò)位排列的公式：n個(gè)不同元素排成一排，第一個(gè)元素不在第一位，第二個(gè)元素不在第二位，第n個(gè)元素不在第n位的排列數(shù)為：A -cnA

17、ni+cX -c3An + +（-i）nc：A這實(shí)際上是公式a -cmAni十cmwj2 此耳+ +（i）mcmAn比的特殊情況.這個(gè)公式很有用，只要有特殊元素不站特殊位置的問題，都可以用這個(gè)公式很快得到解決，希望這個(gè)公式對(duì)大家有所幫助五.圓桌排列從n個(gè)不同元素中不重復(fù)的取出 m （iMmWn）個(gè)元素排在一個(gè)圓周上，叫做這 n個(gè)不同元素的圓排列.如果一個(gè)m-圓排列旋轉(zhuǎn)可以得到另一個(gè) m-圓排列，則認(rèn)為這兩個(gè)圓排列是相同的.特別的，當(dāng) m = n時(shí)，n個(gè)不同元素作成的圓排列總數(shù)為（n-1）!.證明：在圓周上任選一個(gè)位置排 2_,有口種排法，再選一個(gè)位置排 22有門-1種排法，最后一個(gè)位置排n!a

18、n有1種排法.而這n個(gè)人順時(shí)針（或逆時(shí)針）挪動(dòng) n次位置都是同一種排列.所以共有一=（n -1）!種排法. n例10有5對(duì)夫婦參加一場(chǎng)婚宴，他們被安排在一張10個(gè)座位的圓桌就餐，但是婚禮操辦者并不知道他們彼此之間的關(guān)系，只是隨機(jī)安排座位。問5對(duì)夫婦恰好都被安排在一起相鄰而坐的概率是多少？（）4!種坐法，而夫婦間又可以換位置，所A.在1%o到5%o之間 B.在5%o到1%之間 C.超過1% D.不超過1%o解：5對(duì)夫婦相鄰而座，可以看做是五個(gè)大元素為桌而坐，所以有.4! 2 2 2 2 229459!n個(gè)人，需要確定最終的三個(gè)“先進(jìn)人物”人以共有 4. 2 2 2 2 2 0.002.故選：A.

19、例11博杰學(xué)習(xí)網(wǎng)競(jìng)賽小組“先進(jìn)人物評(píng)比”最終圈定了選.方法是：這n個(gè)人排成一行，從第一名開始，1至3循環(huán)報(bào)數(shù)，凡報(bào)出 3的就退出，余下的向前靠攏，按此規(guī)律重復(fù)進(jìn)行.直到第p次報(bào)數(shù)后，只剩下 3個(gè)人為止.試問：這剩下的三個(gè)人，分別在隊(duì)伍最初的什么位置？解：設(shè)n個(gè)人的編號(hào)依次為 1,2,，n.最后剩下的三個(gè)人中，第三人的編號(hào)為bn.因bn未被淘汰，故不是3的倍數(shù).第一次報(bào)數(shù)后淘汰了 一個(gè)人，還剩n -個(gè)人.bn向前移動(dòng)了 bn-bk （k = n-"n）個(gè)人，前面 333淘汰了 bn =bn rn（rn=1,2 ）個(gè)人.故bn=3bk一rn.其中當(dāng)bk為奇數(shù)時(shí)，rn =1 ；否則，rn=

20、 2,每報(bào)一次321號(hào)，人數(shù)減少-（除不盡時(shí)取整）.計(jì)算bn逐步歸納為減小的數(shù)列，最終劃歸到小情況.例如n =1000時(shí)，第3三個(gè)人的初始位置是 712.例12 將圓分成n ( n圭2)個(gè)扇形，現(xiàn)用 m ( m至2)種顏色給這些扇形染色，每個(gè)扇形恰染一種顏色 且要求相鄰的扇形不同色.問有多少種不同的染色方法？解：設(shè)染色方法數(shù)為 an.(1)求初始值.當(dāng)n=2時(shí)，給§染色有m種方法，給 &染色有m-1種方法.所以 a2 =m(m -1)；(2)求遞推關(guān)系.給§染色有m種方法，給 &染色有m-1種方法，給S染色有m-1種方法，給Sn染色有m-1種方法.共有m(m

21、-1)n種方法.這種情況可以分為兩類一類是Sn與S,不同色，此時(shí)的染色方法種數(shù)是an ；另一類是Sn與S同色，Sn與S可以合并為一個(gè)扇形，與S不同色，染色方法種數(shù)為 an.由加法原理，得到n 1an +an=m(m1)( n >2).(3)求an.構(gòu)造等比數(shù)列.結(jié)論：共有an =(m1)n+(1)n(m1)種染色方法.六.轉(zhuǎn)化命題對(duì)于一些較難的排列組合問題，通常采用轉(zhuǎn)化命題的方法來解決.比如圓內(nèi)弦的交點(diǎn)個(gè)數(shù)可轉(zhuǎn)化為圓內(nèi)接四邊形的個(gè)數(shù)；異面直線的對(duì)數(shù)可轉(zhuǎn)化為3倍的四面體的個(gè)數(shù)等.例13圓周上共有15個(gè)不同的點(diǎn)，過其中任意兩點(diǎn)連一弦，這些弦在圓內(nèi)的交點(diǎn)最多有多少個(gè)？分析：若兩弦有交點(diǎn)，則兩弦

22、應(yīng)是圓內(nèi)接四邊形的對(duì)角線，即一個(gè)四邊形對(duì)應(yīng)一個(gè)交點(diǎn).所以共有C15 =1365個(gè)交點(diǎn).小結(jié)：1 . “在”與“不在”可以相互轉(zhuǎn)化.解決某些元素在某些位置上用“定位法”，解決某些元素不在某些位置上一般用“間接法”或轉(zhuǎn)化為“在”的問題求解2 .排列組合應(yīng)用題極易出現(xiàn)“重”、“漏”現(xiàn)象，而“重”、“漏”錯(cuò)誤常發(fā)生在該不該分類、有無順序的問 題上.為了更好地防“重”堵“漏”，在做題時(shí)需認(rèn)真分析自己做題思路，也可改變解題角度，利用一題多解核 對(duì)答案.【作業(yè)】1 .今有8個(gè)人坐圓桌，有多少種坐法？2 .有5個(gè)男孩，3個(gè)女孩圍成一圓，其中 3個(gè)女孩不相鄰，有多少種站法？3 . 一圓型餐桌依次有 A、B、C、

23、D、E、F六個(gè)座位，現(xiàn)讓 3個(gè)大人和3個(gè)孩子入座進(jìn)餐，要求任何兩個(gè)小孩都不能坐在一起，則不同的作法總數(shù)為72 .七.用容斥原理解排列問題有些排列組合問題可轉(zhuǎn)化為求集合的元素的個(gè)數(shù)來求.充分應(yīng)用容斥原理：n(A IjB) =n(A) n(B) -n(ApB)n(A LB LC)=n(A) n(B) n(C) -n(ApB) -n(BDc)-n(ApB) n(AB! C).例14五人站成一排，其中甲不站第一位，乙不立第二位，共有多少種不同的站法解：這個(gè)問題在高中很多參考書上都有，有幾種解法，其中一解法是用排除法：先考慮5個(gè)有的全排列,544有A5種不同的排法，然后除去甲排第一(有 A種)與乙排第二

24、(也有 A種)，但兩種又有重復(fù)部分，因此多減，必須加上多減部分，這樣得到共有：A -2A4 +a =78種.例15 有5個(gè)人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少種不同的站法.仿上分析可得： A5 -3A4 +3A3 - A； =64種.八.均勻分組問題.般地：將mn個(gè)不同元素均勻分成n組(每組m個(gè)元素)，共有Cm CmCmCmn Cmn -mCm種方法.例16 有6本不同的書，按下列要求各有多少種不同的選法：(1)分給甲、乙、丙三人，每人 2本；(2)分為三份，每份2本；(3)分為三份，一份 1本，一份2本，一份3本；(4)分給甲、乙、丙三人，一人 1本，一人2本，

25、一人3本;(5)分給甲、乙、丙三人，每人至少1本.解：(1)根據(jù)分步計(jì)數(shù)原理得到：C；C2C； =90種；(2)分給甲、乙、丙三人，每人兩本有Cf2C42C2種方法，這個(gè)過程可以分兩步完成：第一步分為三份,每份兩本，設(shè)有X種方法；第二步再將這三份分給甲、乙、丙三名同學(xué)有A；種方法.根據(jù)分步計(jì)數(shù)原理可得:c；c2c；= xC，所以 x = C62c干2 =15.A因此，分為三份，每份兩本一共有15種方法.(3)這是“不均勻分組”問題，一共有C6C；C； =60種方法.653(4)在(3)的基礎(chǔ)上再進(jìn)行全排列，所以一共有C6C；C；A； =360種方法.(5)可以分為三類情況：“2、2、2型”即(

26、1)中的分配情況，有 C2C42CI =90種方法;“1、2、3型”即(4)中的分配情況，有 C6C；C；A3 =360種方法;“1、1、4型”，有C：A； =90種方法；所以，一共有 90+360+90= 540種方法.點(diǎn)評(píng)：本題第(3)種類型為部分均勻分組再分配，其分組總數(shù)為C&G1A2題型變換：8名球員住A、B、C三個(gè)房間，每個(gè)房間最多住 3人，有多少種住宿方法?解：A3.例17 若3名飛行員和6名特勤人員分別上 3架不同型號(hào)的直升飛機(jī)執(zhí)行任務(wù)，每機(jī)一名飛行員和兩名特勤人員，有多少種分配方法?解：先分組，再分配,2 2 2 1 1 1 一 一C6C4 c2 C3C2c133A F

27、 A A3 或者 c62c：c2 Cc；c；.類題：20名同學(xué)分兩組，每組10人去某地社會(huì)實(shí)踐，其中 6名干部，每組3人，不同分法總數(shù)是多少？ 37答案:C6與A2 .A2 A九.隔板法：將n個(gè)相同元素，分成k (n之k, n, k= N )組，可以看成是在 n個(gè)元素之間的n-1個(gè) 空隙間插入k -1塊隔板.共有C：種方法.例18 將六本相同的書全部發(fā)給甲、乙、丙三人 .(1)每人至少分到一本書，問有多少種不同的分法？(2)每人不一定都分到一本書，問有多少種不同的分法？解：(1)用“隔板法”處理，六本書之間有五個(gè)空，插入兩塊隔板，有C；種分法；用“隔板站位法”處理，六本書之間有五個(gè)空，需插入兩

28、塊隔板，但由于有人可能沒有書，所以兩塊隔板站著兩個(gè)位置，加上六本書，可以看著是6+2 =8本書，分成3分，所以有CjnC： =28種分法.點(diǎn)評(píng)：類類題1求不定方程Xi +X2 +X3 =6的非負(fù)整數(shù)解的個(gè)數(shù)?題型變換一：四本不同的書，分給三個(gè)人，每人至少一本，全部分完，有幾種分法？解：先分組，再分配有 c：a3種.題型變換二：n本不同的書，分給 n-1個(gè)人，每人至少1本，全部分完，有幾種分法？解：先分組，再分配有 C12Al二種.題型變換三：n本相同的書，全部分給 m (m<n)個(gè)人.(1)每人至少分到一本書，問有多少種不同的分法？(2)每人不一定都分到一本書，問有多少種不同的分法？解：

29、(1)解法一(隔板站位法)：每人先分一本書，還剩下n-m本書，加上 m-1塊隔板，可視為(n -m)+(m -1) = n -1本書，分給m個(gè)人，所以有Cm：種方法.解法二(隔板法)：n本書之間有n-1個(gè)空，需插入 m-1塊隔板，所以有 Cmf種方法.(2)(隔板站位法)：n本書之間，需插入 m-1塊隔板，但是，由于有人分不到書，所以 m-1塊隔板站 著m-1個(gè)位置，加上n本書，可視為n+m-1本書，用m-1塊隔板分成 m分，所以有Cnmm種方法(這也 是一個(gè)公式).【隨堂練習(xí)】1. (1)四個(gè)不同的小球放入四個(gè)不同的盒中，一共有多少種不同的放法？(2)四個(gè)不同的小球放入四個(gè)不同的盒中且恰有一

30、個(gè)空盒的放法有多少種？解：(1)根據(jù)分步計(jì)數(shù)原理：一共有 44 =256種方法；(2)(捆綁法)第一步：從四個(gè)不同的小球中任取兩個(gè)“捆綁”在一起看成一個(gè)元素有C42種方法；第二步：從四個(gè)不同的盒中任取三個(gè)將球放入有A：種方法，所以，一共有 C42 A43 = 144種方法.說明：先組合，再排列是解決問題的關(guān)鍵.本題亦可先將4個(gè)小球分成三組，每組分別有 1/1/ 2個(gè)，共再放入四個(gè)盒子中的三個(gè)，共有 C4C2C1 a3 =144種.A2思考：(1)四個(gè)相同的小球放入四個(gè)不同的盒子中，一共有多少種不同的放法?解：(隔板站位法)共C：+=C3=35.(2) 10個(gè)相同的小球放入編號(hào)為 1、2、3的盒

31、子中，球數(shù)不少于編號(hào)數(shù)的放法有多少種？解：按要求放6個(gè)，其余4個(gè)按隔板站位法 有C：w =C： =15種方法.另解：(隔板法)設(shè)1, 2, 3號(hào)盒子所放的千數(shù)分別為 a, b, c.則有a + b + c = 10.設(shè)乂 = 2, y=b-1, z = c-2,則方程x + y+z = 7的正整數(shù)解的組數(shù)，就是放球的方法數(shù).所以共有22C4 H2 =C6 =15種方法.注意：這種利用“先換元，再用隔板技巧”的方法對(duì)于求有限制條件的不定方程的非負(fù)整數(shù)解的問題很有效！【總結(jié)提煉】均勻分組(不計(jì)組的順序)問題不是簡(jiǎn)單的組合問題，如：將3個(gè)人分成3組，每組一個(gè)人，顯然只有1種分法，而不是=6種.cmc

32、mcm一般地，將 m n個(gè)不同元素均勻分成 n組，有()： 一m種分法；Am十.窮舉法：對(duì)于一些不能直接用兩個(gè)原理，且類別不多的問題，通常采用窮舉法.即列舉所有情況.例19將五個(gè)市級(jí)三好學(xué)生名額和八個(gè)區(qū)級(jí)優(yōu)秀學(xué)生干部名額全部分配到轄區(qū)的兩所中學(xué)，每所學(xué)校至少有一個(gè)名額，有多少種不同的分配方案？解：分配情況用有序數(shù)組 (x, y)表示:(1,12), (2,11 ), (3,10), (4,9), (5,8), (6,7).然后兩校交換所以共有分配方案數(shù)為 2 M(2 + 3+4十5十6+6)=52種.例20 .十一.遞推法：對(duì)于一些較復(fù)雜的排列問題，可以建立排法之間的一個(gè)遞推關(guān)系，通過遞推關(guān)系

33、求出排法種數(shù)例19 一個(gè)樓梯共10個(gè)臺(tái)階，如果規(guī)定一步登一個(gè)臺(tái)階或登兩個(gè)臺(tái)階，一共有多少種不同的走法？解：設(shè)上n級(jí)臺(tái)階的走法為an種，易知a1 =1, a2 = 2 ,當(dāng)n至2時(shí)，上n級(jí)臺(tái)階的走法可分兩類：第一類是最后一步跨一級(jí)，有an q種走法，第二類是最后一步跨二級(jí)，有ani種走法.由加法原理可知an=an4+an/，據(jù)此可得a10=89種不同的走法.例20 有五個(gè)人排成一列，現(xiàn)在要重新排列，要求都不能站在原來的位置，有幾種不同排法？.設(shè)滿足這解：我們考慮人數(shù)為 n的情況，即n個(gè)人排成一列，重新站隊(duì)時(shí)，各人都不站在原來的位置上樣的站隊(duì)方式有an種，現(xiàn)在我們來通過合理分步，恰當(dāng)分類找出遞推關(guān)

34、系：第一步：第一個(gè)人不站在原來的第一個(gè)位置，有 n1種站法.第二步：假設(shè)第一個(gè)人站在第2個(gè)位置，則第二個(gè)人的站法又可以分為兩類：第一類，第二個(gè)人恰好站在第一個(gè)位置，則余下的n2個(gè)人有an/種站隊(duì)方式；第二類，第二個(gè)人不站在第一個(gè)位置，則就是第二個(gè)人不站在第一個(gè)位置，第三個(gè)人不站在第三個(gè)位置, 第四個(gè)人不站在第四個(gè)位置，第n個(gè)人不站在第n個(gè)位置，所以有an_1種站隊(duì)方式.由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理，我們便得到了數(shù)列K的遞推關(guān)系式：an =(n 1)3,+an/),顯然，2=0, a2=1,，a5=44.故有 44種不同排法.注意：n個(gè)人排成一排后，解散后重新排隊(duì)，自己不站原來的位置的排法種數(shù)可

35、由以下公式推導(dǎo)得到:(1) & =0, %=1, an=(n - 1)(an* an_2)( n - 3 );(2)an1= n!1 -1!11n 1(1)-. 2! 3!n! an =a -cnA+cnx-Cn3AnE+(-1)ncnx.例21在n=<m的網(wǎng)格中，從(0,0)點(diǎn)到(n, m)點(diǎn)，只能沿網(wǎng)格的邊向 x軸正方向或y軸正方向前進(jìn)，問共有多少種不同的前進(jìn)路線？解：對(duì)任意一個(gè)非 x軸、y軸上的點(diǎn)(x,y),可以從點(diǎn)(x,y1)走來，也可以從點(diǎn)(x 1,y)走來.因此,設(shè)(x, y)處的路線條數(shù)為f(x, y),則有遞推公式:f(x, y) - f(x, y -1) f (

36、x -1, y).下面的推理很重要：根據(jù)上述遞推公式，可得f (x, y) =cxx+y,即從x + y件物品中選出無順序的 x件(或(x y)!y件)的總方案數(shù).即f (x, y) = (紇.x!y!小結(jié)：上述問題中把每個(gè)f(x,y)指標(biāo)在對(duì)應(yīng)的坐標(biāo)點(diǎn)處，再將坐標(biāo)系順時(shí)針旋轉(zhuǎn)135°,你發(fā)現(xiàn)了什么？這是楊輝三角，f (x, y) =Cx4y.而我們知道，C： = CL +C：”這就是通項(xiàng)公式的來源.另解：記網(wǎng)格橫向的x條線段從左至右依次為a1、a2、ax,網(wǎng)格縱向的y條線段從下至上依次為 b、b2、by.從(0,0)至U(x, y)的走法種數(shù)，就是為、a?、ax及b、b2、by這x+y個(gè)元素的一個(gè)N y定序排列.于是有 m (或(x+y)!)種不同走法.Ax Ayx!y!例22某地決定在一個(gè)大型廣場(chǎng)建一個(gè)同心圓形花壇，花壇分為兩部分，中間小圓部分種植草坪