高等排列組合問題的解題技巧

（一）排序問題1.相鄰問題捆綁法:題目中規(guī)定相鄰的幾個元素捆綁成一個組，當(dāng)作一個大元素參與排列.例1.五人并排站成一排，如果必須相鄰且在的右邊，則不同的排法有（）A、60種B、48種C、36種D、24種解析：把視為一人，且固定在的右邊，則本題相當(dāng)于4人的全排列，種，答案：.2.相離問題插空排:元素相離（即不相鄰）問題，可先把無位置要求的幾個元素全排列，再把規(guī)定的相離的幾個元素插入上述幾個元素的空位和兩端.例2.七人并排站成一行，如果甲乙兩個必須不相鄰，那么不同的排法種數(shù)是（）A、1440種B、3600種C、4820種D、4800種解析：除甲乙外，其余5個排列數(shù)為種，再用甲乙去插6個空位有種，不同的排法種數(shù)是種，選.3.定序問題縮倍法:在排列問題中限制某幾個元素必須保持一定的順序，可用縮小倍數(shù)的方法.例3.A,B,C,D,E五人并排站成一排，如果必須站在的右邊（可以不相鄰）那么不同的排法有（）A、24種B、60種C、90種D、120種解析：在的右邊與在的左邊排法數(shù)相同，所以題設(shè)的排法只是5個元素全排列數(shù)的一半，即種，選.11.定位問題優(yōu)先法：某個或幾個元素要排在指定位置，可先排這個或幾個元素；再排其它的元素。例11.現(xiàn)有1名老師和4名獲獎同學(xué)排成一排照相留念，若老師不站兩端則有不同的排法有多少種？解析：老師在中間三個位置上選一個有種，4名同學(xué)在其余4個位置上有種方法；所以共有種。12.多排問題單排法:把元素排成幾排的問題可歸結(jié)為一排考慮，再分段處理。例12.（1）6個不同的元素排成前后兩排，每排3個元素，那么不同的排法種數(shù)是（）A、36種B、120種C、720種D、1440種（2）8個不同的元素排成前后兩排，每排4個元素，其中某2個元素要排在前排，某1個元素排在后排，有多少種不同排法？解析：（1）前后兩排可看成一排的兩段，因此本題可看成6個不同的元素排成一排，共種，選.（2）解析：看成一排，某2個元素在前半段四個位置中選排2個，有種，某1個元素排在后半段的四個位置中選一個有種，其余5個元素任排5個位置上有種，故共有種排法.16.圓排問題單排法:把個不同元素放在圓周個無編號位置上的排列，順序（例如按順時鐘）不同的排法才算不同的排列，而順序相同（即旋轉(zhuǎn)一下就可以重合）的排法認為是相同的，它與普通排列的區(qū)別在于只計順序而無首位、末位之分，下列個普通排列：在圓排列中只算一種，因為旋轉(zhuǎn)后可以重合，故認為相同，個元素的圓排列數(shù)有種.因此可將某個元素固定展成單排，其它的元素全排列.例16.有5對姐妹站成一圈，要求每對姐妹相鄰，有多少種不同站法？解析：首先可讓5位姐姐站成一圈，屬圓排列有種，然后在讓插入其間，每位均可插入其姐姐的左邊和右邊，有2種方式，故不同的安排方式種不同站法.說明：從個不同元素中取出個元素作圓形排列共有種不同排法.17.可重復(fù)的排列求冪法:允許重復(fù)排列問題的特點是以元素為研究對象，元素不受位置的約束，可逐一安排元素的位置，一般地個不同元素排在個不同位置的排列數(shù)有種方法.例17.把6名實習(xí)生分配到7個車間實習(xí)共有多少種不同方法？解析：完成此事共分6步，第一步；將第一名實習(xí)生分配到車間有7種不同方案，第二步：將第二名實習(xí)生分配到車間也有7種不同方案，依次類推，由分步計數(shù)原理知共有種不同方案.14.選排問題先取后排:從幾類元素中取出符合題意的幾個元素，再安排到一定的位置上，可用先取后排法.例14.（1）四個不同球放入編號為1，2，3，4的四個盒中，則恰有一個空盒的放法有多少種？（2）9名乒乓球運動員，其中男5名，女4名，現(xiàn)在要進行混合雙打訓(xùn)練，有多少種不同的分組方法？解析：先取四個球中二個為一組，另二組各一個球的方法有種，再排：在四個盒中每次排3個有種，故共有種.解析：先取男女運動員各2名，有種，這四名運動員混和雙打練習(xí)有種排法，故共有種.4.標號排位問題分步法:把元素排到指定位置上，可先把某個元素按規(guī)定排入，第二步再排另一個元素，如此繼續(xù)下去，依次即可完成.例4.將數(shù)字1，2，3，4填入標號為1，2，3，4的四個方格里，每格填一個數(shù)，則每個方格的標號與所填數(shù)字均不相同的填法有（）A、6種B、9種C、11種D、23種解析：先把1填入方格中，符合條件的有3種方法，第二步把被填入方格的對應(yīng)數(shù)字填入其它三個方格，又有三種方法；第三步填余下的兩個數(shù)字，只有一種填法，共有3×3×1=9種填法，選.22.全錯位排列問題公式法:全錯位排列問題（賀卡問題，信封問題）記住公式即可瑞士數(shù)學(xué)家歐拉按一般情況給出了一個遞推公式：用A、B、C……表示寫著n位友人名字的信封，a、b、c……表示n份相應(yīng)的寫好的信紙。把錯裝的總數(shù)為記作f(n)。假設(shè)把a錯裝進B里了，包含著這個錯誤的一切錯裝法分兩類：（1）b裝入A里，這時每種錯裝的其余部分都與A、B、a、b無關(guān)，應(yīng)有f(n-2)種錯裝法。（2）b裝入A、B之外的一個信封，這時的裝信工作實際是把（除a之外的）份信紙b、c……裝入（除B以外的）n－1個信封A、C……，顯然這時裝錯的方法有f(n-1)種?？傊赼裝入B的錯誤之下，共有錯裝法f(n-2)+f(n-1)種。a裝入C，裝入D……的n－2種錯誤之下，同樣都有f(n-2)+f(n-1)種錯裝法，因此:得到一個遞推公式：f(n)=(n-1){f(n-1)+f(n-2)}，分別代入n=2、3、4等可推得結(jié)果。也可用迭代法推導(dǎo)出一般公式：例.五位同學(xué)坐在一排，現(xiàn)讓五位同學(xué)重新坐，至多有兩位同學(xué)坐自己原來的位置，則不同的坐法有種.解析：可以分類解決：第一類，所有同學(xué)都不坐自己原來的位置；第二類，恰有一位同學(xué)坐自己原來的位置；第三類，恰有兩位同學(xué)坐自己原來的位置.對于第一類，就是上面講的全錯位排列問題；對于第二、第三類有部分元素還占有原來的位置，其余元素可以歸結(jié)為全錯位排列問題，我們稱這種排列問題為部分錯位排列問題.設(shè)n個元素全錯位排列的排列數(shù)為Tn，則對于例3，第一類排列數(shù)為T5，第二類先確定一個排原來位置的同學(xué)有5種可能，其余四個同學(xué)全錯位排列，所以第二類的排列數(shù)為5T4，第三類先確定兩個排原位的同學(xué)，有=10種，所以第三類的排列數(shù)為10T3，因此例3的答案為：T5+5T4+10T3.（二）分組分配問題24．平均分堆問題去除重復(fù)法例2.從7個參加義務(wù)勞動的人中，選出6個人，分成兩組，每組都是3人，有多少種不同的分法？分析：記7個人為a、b、c、d、e、f、g寫出一些組來考察。表1選3人再選3人分組方法種數(shù)abcdefdefabc這兩種只能算一種分法abcdegdegabc這兩種只能算一種分法………………由表1可見，把abc，def看作2個元素順序不同的排列有種，而這只能算一種分組方法。解：選3人為一組有種，再選3人為另一組有種，依分步計數(shù)原理，又每種分法只能算一種，所以不同的分法有（種）。也可以先選再分組為＝70（種）例66本不同的書平均分成三堆，有多少種不同的方法？分析：分出三堆書（a1,a2）,(a3,a4)，（a5,a6）由順序不同可以有=6種，而這6種分法只算一種分堆方式，故6本不同的書平均分成三堆方式有=15種練習(xí)：1．6本書分三份，2份1本，1份4本，則有不同分法？2．某年級6個班的數(shù)學(xué)課，分配給甲乙丙三名數(shù)學(xué)教師任教，每人教兩個班，則分派方法的種數(shù)。5.有序分配問題逐分法:有序分配問題指把元素分成若干組，可用逐步下量分組法.例5.（1）有甲乙丙三項任務(wù)，甲需2人承擔(dān)，乙丙各需一人承擔(dān)，從10人中選出4人承擔(dān)這三項任務(wù)，不同的選法種數(shù)是（）A、1260種B、2025種C、2520種D、5040種（2）12名同學(xué)分別到三個不同的路口進行流量的調(diào)查，若每個路口4人，則不同的分配方案有（）A、種B、種C、種D、種解析：（1）先從10人中選出2人承擔(dān)甲項任務(wù)，再從剩下的8人中選1人承擔(dān)乙項任務(wù)，第三步從另外的7人中選1人承擔(dān)丙項任務(wù)，不同的選法共有種，選.（2）答案：.6.全員分配問題分組法:例6.（1）4名優(yōu)秀學(xué)生全部保送到3所學(xué)校去，每所學(xué)校至少去一名，則不同的保送方案有多少種？（2）5本不同的書，全部分給4個學(xué)生，每個學(xué)生至少一本，不同的分法種數(shù)為（）A、480種B、240種C、120種D、96種答案：（1）36.(2).7.名額分配問題隔板法(無差別物品分配問題隔板法):例7：10個三好學(xué)生名額分到7個班級，每個班級至少一個名額，有多少種不同分配方案？解析：10個名額分到7個班級，就是把10個名額看成10個相同的小球分成7堆，每堆至少一個，可以在10個小球的9個空位中插入6塊木板，每一種插法對應(yīng)著一種分配方案，故共有不同的分配方案為種.8.限制條件的分配問題分類法:例8.某高校從某系的10名優(yōu)秀畢業(yè)生中選4人分別到西部四城市參加中國西部經(jīng)濟開發(fā)建設(shè)，其中甲同學(xué)不到銀川，乙不到西寧，共有多少種不同派遣方案？解析：因為甲乙有限制條件，所以按照是否含有甲乙來分類，有以下四種情況：①若甲乙都不參加，則有派遣方案種；②若甲參加而乙不參加，先安排甲有3種方法，然后安排其余學(xué)生有方法，所以共有；③若乙參加而甲不參加同理也有種；④若甲乙都參加，則先安排甲乙，有7種方法，然后再安排其余8人到另外兩個城市有種，共有方法.所以共有不同的派遣方法總數(shù)為種.（三）排列組合問題中的技巧10.交叉問題集合法（容斥原理）：某些排列組合問題幾部分之間有交集，可用集合中求元素個數(shù)公式例10.從6名運動員中選出4人參加4×100米接力賽，如果甲不跑第一棒，乙不跑第四棒，共有多少種不同的參賽方案？解析：設(shè)全集=｛6人中任取4人參賽的排列｝，A=｛甲跑第一棒的排列｝，B=｛乙跑第四棒的排列｝，根據(jù)求集合元素個數(shù)的公式得參賽方法共有：種.13.“至少”“至多”問題用間接排除法或分類法:例13.從4臺甲型和5臺乙型電視機中任取3臺，其中至少要甲型和乙型電視機各一臺，則不同的取法共有（）A、140種B、80種C、70種D、35種解析1：逆向思考，至少各一臺的反面就是分別只取一種型號，不取另一種型號的電視機，故不同的取法共有種,選.解析2：至少要甲型和乙型電視機各一臺可分兩種情況：甲型1臺乙型2臺；甲型2臺乙型1臺；故不同的取法有臺,選.23．構(gòu)造數(shù)列遞推法例一樓梯共10級，如果規(guī)定每次只能跨上一級或兩級，要走上這10級樓梯，共有多少種不同的走法？分析：設(shè)上n級樓梯的走法為an種，易知a1=1,a2=2,當(dāng)n≥2時，上n級樓梯的走法可分兩類：第一類：是最后一步跨一級，有an-1種走法，第二類是最后一步跨兩級，有an-2種走法，由加法原理知：an=an-1+an-2,據(jù)此，a3=a1+a2=3,a4=a#+a2=5,a5=a4+a3=8,a6=13,a7=21,a8=34,a9=55,a10=89.故走上10級樓梯共有89種不同的方法。15.部分合條件問題排除法:在選取的總數(shù)中，只有一部分合條件，可以從總數(shù)中減去不符合條件數(shù)，即為所求.例15.（1）以正方體的頂點為頂點的四面體共有（）A、70種B、64種C、58種D、52種（2）四面體的頂點和各棱中點共10點，在其中取4個不共面的點，不同的取法共有（）A、150種B、147種C、144種D、141種解析：（1）正方體8個頂點從中每次取四點，理論上可構(gòu)成四面體，但6個表面和6個對角面的四個頂點共面都不能構(gòu)成四面體，所以四面體實際共有個.（2）解析：10個點中任取4個點共有種，其中四點共面的有三種情況：①在四面體的四個面上，每面內(nèi)四點共面的情況為，四個面共有個；②過空間四邊形各邊中點的平行四邊形共3個；③過棱上三點與對棱中點的三角形共6個.所以四點不共面的情況的種數(shù)是種.18.復(fù)雜排列組合問題構(gòu)造模型法:例18.馬路上有編號為1，2，3…，9九只路燈，現(xiàn)要關(guān)掉其中的三盞，但不能關(guān)掉相鄰的二盞或三盞，也不能關(guān)掉兩端的兩盞，求滿足條件的關(guān)燈方案有多少種？解析：把此問題當(dāng)作一個排隊模型，在6盞亮燈的5個空隙中插入3盞不亮的燈種方法,所以滿足條件的關(guān)燈方案有10種.說明：一些不易理解的排列組合題，如果能轉(zhuǎn)化為熟悉的模型如填空模型，排隊模型，裝盒模型可使問題容易解決.19.元素個數(shù)較少的排列組合問題可以考慮枚舉法:例19.設(shè)有編號為1，2，3，4，5的五個球和編號為1，2，3，4，5的盒子現(xiàn)將這5個球投入5個盒子要求每個盒子放一個球，并且恰好有兩個球的號碼與盒子號碼相同，問有多少種不同的方法？解析：從5個球中取出2個與盒子對號有種，還剩下3個球與3個盒子序號不能對應(yīng)，利用枚舉法分析，如果剩下3，4，5號球與3，4，5號盒子時，3號球不能裝入3號盒子，當(dāng)3號球裝入4號盒子時，4，5號球只有1種裝法，3號球裝入5號盒子時，4，5號球也只有1種裝法，所以剩下三球只有2種裝法，因此總共裝法數(shù)為種.9.多元問題分類法：元素多，取出的情況也多種，可按結(jié)果要求分成不相容的幾類情況分別計數(shù)再相加。例9（1）由數(shù)字0，1，2，3，4，5組成沒有重復(fù)數(shù)字的六位數(shù)，其中個位數(shù)字小于十位數(shù)字的共有（）A、210種B、300種C、464種D、600種（2）從1，2，3…，100這100個數(shù)中，任取兩個數(shù)，使它們的乘積能被7整除，這兩個數(shù)的取法（不計順序）共有多少種？（3）從1，2，3，…，100這100個數(shù)中任取兩個數(shù)，使其和能被4整除的取法（不計順序）有多少種？解析：(1)按題意，個位數(shù)字只可能是0，1，2，3，4共5種情況，分別有個，個，合并總計300個,選.另解，首位數(shù)字不能為0，故首位數(shù)字有5種選擇，其它五個數(shù)字全排列，由于個位數(shù)字比十位數(shù)字大與個位數(shù)字比十位數(shù)字小是對稱的。故所求六位數(shù)共有5/2=300。（2）解析：被取的兩個數(shù)中至少有一個能被7整除時，他們的乘積就能被7整除，將這100個數(shù)組成的集合視為全集I,能被7整除的數(shù)的集合記做共有14個元素,不能被7整除的數(shù)組成的集合記做共有86個元素；由此可知，從中任取2個元素的取法有，從中任取一個，又從中任取一個共有，兩種情形共符合要求的取法有種.（3）解析：將分成四個不相交的子集，能被4整除的數(shù)集；能被4除余1的數(shù)集，能被4除余2的數(shù)集，能被4除余3的數(shù)集，易見這四個集合中每一個有25個元素；從中任取兩個數(shù)符合要；從中各取一個數(shù)也符合要求；從中任取兩個數(shù)也符合要求；此外其它取法都不符合要求；所以符合要求的取法共有種.20.復(fù)雜的排列組合問題也可用分解與合成法:例20.（1）30030能被多少個不同偶數(shù)整除？（2）正方體8個頂點可連成多少對異面直線？解析：先把30030分解成質(zhì)因數(shù)的形式：30030=2×3×5×7×11×13；依題意偶因數(shù)2必取，3，5，7，11，13這5個因數(shù)中任取若干個組成成積，所有的偶因數(shù)為個.（2）解析：因為四面體中僅有3對異面直線，可將問題分解成正方體的8個頂點可構(gòu)成多少個不同的四面體，從正方體8個頂點中任取四個頂點構(gòu)成的四面體有個，所以8個頂點可連成的異面直線有3×58=174對.21.利用對應(yīng)思想轉(zhuǎn)化法:對應(yīng)思想是教材中滲透的一種重要的解題方法，它可以將復(fù)雜的問題轉(zhuǎn)化為簡單問題處理.例21.（1）圓周上有10點，以這些點為端點的弦相交于圓內(nèi)的交點有多少個？（2）某城市的街區(qū)有12個全等的矩形組成，其中實線表示馬路，從A到B的最短路徑有多少種？解析：因為圓的一個內(nèi)接四邊形的兩條對角線相交于圓內(nèi)一點，一個圓的內(nèi)接四邊形就對應(yīng)著兩條弦相交于圓內(nèi)的一個交點，于是問題就轉(zhuǎn)化為圓周上的10個點可以確定多少個不同的四邊形，顯然有個，所以圓周上有10點，以這些點為端點的弦相交于圓內(nèi)的交點有個.（2）解析：可將圖中矩形的一邊叫一小段，從到最短路線必須走7小段，其中：向東4段，向北3段；而且前一段的尾接后一段的首，所以只要確定向東走過4段的走法，便能確定路徑，因此不同走法有種.例17圓周上共有15個不同的點，過其中任意兩點連一弦，這些弦在圓內(nèi)的交點最多有多少各？分析：因兩弦在圓內(nèi)若有一交點，則該交點對應(yīng)于一個以兩弦的四端點為頂點的圓內(nèi)接四邊形，則問題化為圓周上的15個不同的點能構(gòu)成多少個圓內(nèi)接四邊形，因此這些現(xiàn)在圓內(nèi)的交點最多有=1365（個）（四）染色問題24．染色問題合并單元格解決八、排列組合中常見模型（一）分組問題由于涉及的面比較廣，所以是排列、組合中的難點。如果只是斷章取義的去教學(xué)，不從根本上去加以理解、歸納，那么就很難正確的解答各類題型，下面通過例題予以淺談。1、非均勻分組所謂“非均勻分組”是指將所有元素分成元素個數(shù)彼此不相等的組。例1.七個人參加義務(wù)勞動，按下列方法分組有多少種不同的分法？（1）分成三組，分別為1人、2人、4人；（2）選出5個人再分成兩組，一組2人，另一組3人。解：（1）選出1人的方法有種，再由剩下的6個人中選出2人的方法有種，剩下的4人為一組有種，依分步計數(shù)原理得分組的方法有（種）（2）可直接從7人中選出2人的方法有種，再由余下的5個人中選3人的方法有種，所以依分步計數(shù)原理，分組的方法有：（種）。也可先選取5人，再分為兩組有（種）。2、均勻分組所謂“均勻分組”是指將所有元素分成所有組元素個數(shù)相等或部分組元素個數(shù)相等的組。(1)全部均勻分組例2.從7個參加義務(wù)勞動的人中，選出6個人，分成兩組，每組都是3人，有多少種不同的分法？分析：記7個人為a、b、c、d、e、f、g寫出一些組來考察。表1選3人再選3人分組方法種數(shù)abcdefdefabc這兩種只能算一種分法abcdegdegabc這兩種只能算一種分法………………由表1可見，把abc，def看作2個元素順序不同的排列有種，而這只能算一種分組方法。解：選3人為一組有種，再選3人為另一組有種，依分步計數(shù)原理，又每種分法只能算一種，所以不同的分法有（種）。也可以先選再分組為＝70（種）(2)部分均勻分組例3.將十個不同的零件分成四堆，每堆分別有2個、2個、2個、4個，有多少種不同的分法？分析：記十個零件為a、b、c、d、e、f、g、h、i、j寫出一些組來考察表2選2個再選2又選2個剩下四個分組方法數(shù)ababcdcdefefcdefabefabcdefcdefabcdabghijghijghijghijghijghij………|…由表可見，把ab、cd、ef看作三個元素順序不同的排列時有種排法，而這種只能算一種分法。解：因為分成2個、2個、2個、4個元素的四個堆，分別為種，由分步計數(shù)原理及每中只能算一種不同的分組方法得（種）由此可見，不論全部均勻分組還是部分均勻分組，如果有m個組的元素是均勻的，都有種順序不同的排法只能算一種分法。3、編號分組(1)非均勻編號分組例4.從7個參加義務(wù)勞動的人中選出2人一組、3人一組，輪流挖土、運土，有多少種分組方法？解：分組的方法有（種）注：由于分組后各組要擔(dān)任不同的工作，這就將不編號的組變?yōu)榫幪柕慕M，只需乘以組數(shù)的全排列即可。(2)部分均勻編號分組例5.有5本不同的書全部分給3人，每人至少一本，有多少種不同的分法？分析：5本不同的書全部分給3人有兩類情況，一類是一人得3本；另外兩人各得1本；另一類是一人得1本，另外兩人各得2本。解：（1）將書分成3本、1本、1本三組，再分給三個人的方法有：（種）（2）將書分成2本、2本、1本三組，再分給三人共有：（種）所以，總的分組方法有60＋90＝150（種）注：此類題型只要先分組再排列即可。例6.已知集合A含有4個元素，集合B含3個元素，現(xiàn)建立從A到B的映射f：A→B，使B中的每個元素在A中都有原象的映射有多少個？解：先把A中的4個元素分成3組，即2個、1個、1個，所有分組方法有種。再把B中的3個元素看成3個位子，然后在3個位子全排有種因此使B中的元素都有原象的映射有36個。(二)全錯位排列問題每個元素都不在自己編號的位置上的排列問題，我們把這種限制條件的排列問題叫做全錯位排列問題.1．錯位排列問題例1.4名同學(xué)各寫一張賀卡，先集中起來，然后每人從中拿出一張別人寫的賀卡，則四張賀卡的不同分配方式共有種.例2.將編號為1，2，3，4的四個小球分別放入編號為1，2，3，4的四個盒子中，要求每個盒子放一個小球，且小球的編號與盒子的編號不能相同，則共有種不同的放法.這兩個問題的本質(zhì)都是每個元素都不在自己編號的位置上的排列問題，我們把這種限制條件的排列問題叫做全錯位排列問題.例3.五位同學(xué)坐在一排，現(xiàn)讓五位同學(xué)重新坐，至多有兩位同學(xué)坐自己原來的位置，則不同的坐法有種.解析：可以分類解決：第一類，所有同學(xué)都不坐自己原來的位置；第二類，恰有一位同學(xué)坐自己原來的位置；第三類，恰有兩位同學(xué)坐自己原來的位置.對于第一類，就是上面講的全錯位排列問題；對于第二、第三類有部分元素還占有原來的位置，其余元素可以歸結(jié)為全錯位排列問題，我們稱這種排列問題為部分錯位排列問題.設(shè)n個元素全錯位排列的排列數(shù)為Tn，則對于例3，第一類排列數(shù)為T5，第二類先確定一個排原來位置的同學(xué)有5種可能，其余四個同學(xué)全錯位排列，所以第二類的排列數(shù)為5T4，第三類先確定兩個排原位的同學(xué)，有=10種，所以第三類的排列數(shù)為10T3，因此例3的答案為：T5+5T4+10T3.由于生活中很多這樣的問題，所以我們有必要探索一下關(guān)于全錯位排列問題的解決方法.2．關(guān)于全錯位排列數(shù)的一個遞推關(guān)系式：Tn=(n-1)(Tn-1+Tn-2)，（n≥3）(1).一般地，設(shè)n個編號為1、2、3、…、i、…、j、…、n的不同元素a1、a2、a3、…、ai、…、aj、…、an，排在一排，且每個元素均不排在與其編號相同的位置，這樣的全錯位排列數(shù)為Tn，則T2=1，T3=2，Tn=(n-1)(Tn-1+Tn-2)，（n≥3）.(2).遞推關(guān)系的確立顯然對于n=1，2時有T1=0，T2=1.當(dāng)n≥3時，在n個不同元素中任取一個元素ai不排在與其編號相對應(yīng)的i位，必排在剩下n-1個位置之一，所以ai有n-1種排法.對ai每一種排法，如ai排在j位，對應(yīng)j位的元素aj的排位總有兩種情況：第一種情況：aj恰好排在i位上，如表（1）123…i…j…najai表（1）此時，ai排在j位，aj排在i位，元素ai，aj排位已定，還剩n-2個元素，每個元素均有一個不能排的位置，它們的排位問題就轉(zhuǎn)化為n-2個元素全錯位排列數(shù)，應(yīng)有Tn-2種；第二種情況：aj不排在i位上，如表（2）123…i…j…naiaaj不排i位表（2）此時，ai仍排在j位，aj不排在i位，則aj有n-1個位置可排，除ai外，還有n-1個元素，每個元素均有一個不能排的位置，問題就轉(zhuǎn)化為n-1個元素全錯位排列，排列數(shù)為Tn-1，由乘法原理和加法原理可得：Tn=(n-1)(Tn-1+Tn-2)，（n≥3）.利用此遞推關(guān)系可以分別算出T4=9，T5=44，所以題三的答案為44+5×9+10×2=109.3．關(guān)于全錯位排列數(shù)的一個通項公式：Tn=（n≥2）.(1).探索規(guī)定=1（n∈N*），試計算以下各式的值：（1）；（2）；（3）.很容易計算三式的值依次為9，44，265.而這與利用上面的遞推關(guān)系式得到的T4，T5，T6剛好吻合，即T4=；T5=；T6=.(2).猜想根據(jù)上面的探索，我們可以猜想n個元素全錯位排列的排列數(shù)為Tn=（n≥2）（*）為了更容易看清其本質(zhì)，我們對這個式子進行變形，得到：Tn===(3).證明（數(shù)學(xué)歸納法）n=2，3時（*）式顯然成立；假設(shè)n=k，k-1時（*）式成立，則當(dāng)n=k+1時，有上面的遞推關(guān)系式可得：Tk+1=k(Tk+Tk-1)=k{+}=k·(k-1)!·{+}=k!·[+k·]=k!·[+（k+1）·]=k!·[+（k+1）·]=k!·[+（k+1）·]=(k+1)!·[+].∴n=k+1時（*）式也成立.由以上過程可知n個元素全錯位排列的排列數(shù)為：Tn===（n≥2）.4.關(guān)于全錯位排列數(shù)的另一個遞推關(guān)系式：Tn=nTn-1+由T2=1，T3=2，T4=9，T5=44，T6=265可得：T3=3T2－1；T4=4T3+1；T5=5T4－1；T6=6T5+1.于是猜想Tn=nTn-1+.證明：由上面已證明的全錯位排列數(shù)公式可知右邊=n·+=n!+·==左邊.所以Tn=nTn-1+.5.點評在解決排列組合問題時，經(jīng)常涉及到全錯位或部分錯位的排列問題，在元素不是很多時，我們可以通過分類討論的方案，對問題進行討論，但當(dāng)元素較多時討論起來非常麻煩，所以掌握了全錯位排列數(shù)的一個通項公式和兩個遞推關(guān)系式，對我們解決這一類問題將帶來很大的方便.（三）高考數(shù)學(xué)中涂色問題的常見解法及策略與涂色問題有關(guān)的試題新穎有趣,近年已經(jīng)在高考題中出現(xiàn)，其中包含著豐富的數(shù)學(xué)思想。解決涂色問題方法技巧性強且靈活多變，因而這類問題有利于培養(yǎng)學(xué)生的創(chuàng)新思維能力、分析問題與觀察問題的能力，有利于開發(fā)學(xué)生的智力。本文擬總結(jié)涂色問題的常見類型及求解方法一.區(qū)域涂色問題根據(jù)分步計數(shù)原理，對各個區(qū)域分步涂色，這是處理染色問題的基本方法。用5種不同的顏色給圖中標①、②、③、④的各部分涂色，每部分只涂一種顏色，相鄰部分涂不同顏色，則不同的涂色方法有多少種？②②①③④分析：先給①號區(qū)域涂色有5種方法，再給②號涂色有4種方法，接著給③號涂色方法有3種，由于④號與①、②不相鄰，因此④號有4種涂法，根據(jù)分步計數(shù)原理，不同的涂色方法有根據(jù)共用了多少種顏色討論，分別計算出各種出各種情形的種數(shù)，再用加法原理求出不同的涂色方法種數(shù)。①②①②2③④⑤⑥分析：依題意只能選用4種顏色，要分四類：（1）②與⑤同色、④與⑥同色，則有；（2）③與⑤同色、④與⑥同色，則有；（3）②與⑤同色、③與⑥同色，則有；（4）③與⑤同色、② 與④同色，則有；（5）②與④同色、③與⑥同色，則有；243124315例3、如圖所示，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著方法共有多少種？分析：依題意至少要用3種顏色當(dāng)先用三種顏色時，區(qū)域2與4必須同色，區(qū)域3與5必須同色，故有種；當(dāng)用四種顏色時，若區(qū)域2與4同色，則區(qū)域3與5不同色，有種；若區(qū)域3與5同色，則區(qū)域2與4不同色，有種，故用四種顏色時共有2種。由加法原理可知滿足題意的著色方法共有+2=24+224=72根據(jù)某兩個不相鄰區(qū)域是否同色分類討論，從某兩個不相鄰區(qū)域同色與不同色入手，分別計算出兩種情形的種數(shù)，再用加法原理求出不同涂色方法總數(shù)。例4用紅、黃、藍、白、黑五種顏色涂在如圖所示的四個區(qū)域內(nèi)，每個區(qū)域涂一種顏色，相鄰兩個區(qū)域涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法？分析：可把問題分為三類：12341234有且僅兩個區(qū)域相同的顏色，即只有一組對角小方格涂相同的顏色，涂法種數(shù)為；兩組對角小方格分別涂相同的顏色，涂法種數(shù)為，因此，所求的涂法種數(shù)為根據(jù)相間區(qū)使用顏色的種類分類例5如圖，6個扇形區(qū)域A、B、C、D、E、F，現(xiàn)給這6個區(qū)域著色，要求同一區(qū)域涂同一種顏色，相鄰的兩個區(qū)域不得使用同一種顏色，現(xiàn)有4種不同的顏色可解（1）當(dāng)相間區(qū)域A、C、E著同一種顏色時，ABABCDEFB、D、F各有3種著色方法，此時，B、D、F各有3種著色方法故有種方法。（2）當(dāng)相間區(qū)域A、C、E著色兩不同的顏色時，有種著色方法，此時B、D、F有種著色方法，故共有種著色方法。（3）當(dāng)相間區(qū)域A、C、E著三種不同的顏色時有種著色方法，此時B、D、F各有2種著色方法。此時共有種方法。故總計有108+432+192=732種方法。說明：關(guān)于扇形區(qū)域區(qū)域涂色問題還可以用數(shù)列中的遞推公來解決。⑤⑤⑤⑤⑤⑤⑤⑤⑤解：設(shè)分成n個扇形時染色方法為種⑤（1）當(dāng)n=2時、有=12種，即=12⑤（2）當(dāng)分成n個扇形，如圖，與不同色，與不同色，，與不同色，共有種染色方法，但由于與鄰，所以應(yīng)排除與同色的情形；與同色時，可把、看成一個扇形，與前個扇形加在一起為個扇形，此時有種染色法，故有如下遞推關(guān)系：二.點的涂色問題方法有：（1）可根據(jù)共用了多少種顏色分類討論，（2）根據(jù)相對頂點是否同色分類討論，（3）將空間問題平面化，轉(zhuǎn)化成區(qū)域涂色問題。例6、將一個四棱錐的每個頂點染上一種顏色，并使同一條棱的兩端點異色，如果只有5種顏色可供使用，那么不同的染色方法的總數(shù)是多少？解法一：滿足題設(shè)條件的染色至少要用三種顏色。（1）若恰用三種顏色，可先從五種顏色中任選一種染頂點S，再從余下的四種顏色中任選兩種涂A、B、C、D四點，此時只能A與C、B與D分別同色，故有種方法。（2）若恰用四種顏色染色，可以先從五種顏色中任選一種顏色染頂點S，再從余下的四種顏色中任選兩種染A與B，由于A、B顏色可以交換，故有種染法；再從余下的兩種顏色中任選一種染D或C，而D與C，而D與C中另一個只需染與其相對頂點同色即可，故有種方法。（3）若恰用五種顏色染色，有種染色法綜上所知，滿足題意的染色方法數(shù)為60+240+120=420種。解法二：設(shè)想染色按S—A—B—C—D的順序進行，對S、A、B染色，有種染色方法。由于C點的顏色可能與A同色或不同色，這影響到D點顏色的選取方法數(shù)，故分類討論：SCDABSCDAB解法三：可把這個問題轉(zhuǎn)化成相鄰區(qū)域不同色問題：如圖，對這五個區(qū)域用5種顏色涂色，有多少種不同的涂色方法？二.線段涂色問題對線段涂色問題，要注意對各條線段依次涂色，主要方法有：根據(jù)共用了多少顏色分類討論根據(jù)相對線段是否同色分類討論。例7、用紅、黃、藍、白四種顏色涂矩形ABCD的四條邊，每條邊只涂一種顏色，且使相鄰兩邊涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法？解法一：（1）使用四顏色共有種;（2）使用三種顏色涂色，則必須將一組對邊染成同色，故有種，（3）使用二種顏色時，則兩組對邊必須分別同色，有種因此，所求的染色方法數(shù)為種解法二：涂色按AB－BC－CD－DA的順序進行，對AB、BC涂色有種涂色方法。由于CD的顏色可能與AB同色或不同色，這影響到DA顏色的選取方法數(shù)，故分類討論：當(dāng)CD與AB同色時，這時CD對顏色的選取方法唯一，則DA有3種顏色可供選擇CD與AB不同色時，CD有兩種可供選擇的顏色，DA也有兩種可供選擇的顏色，從而對CD、DA涂色有種涂色方法。由乘法原理，總的涂色方法數(shù)為種例8、用六種顏色給正四面體的每條棱染色，要求每條棱只染一種顏色且共頂點的棱涂不同的顏色，問有多少種不同的涂色方法？解：（1）若恰用三種顏色涂色，則每組對棱必須涂同一顏色，而這三組間的顏色不同，故有種方法。（2）若恰用四種顏色涂色，則三組對棱中有二組對棱的組內(nèi)對棱涂同色，但組與組之間不同色，故有種方法。（3）若恰用五種顏色涂色，則三組對棱中有一組對棱涂同一種顏色，故有種方法。（4）若恰用六種顏色涂色，則有種不同的方法。綜上，滿足題意的總的染色方法數(shù)為種。三.面涂色問題例9、從給定的六種不同顏色中選用若干種顏色，將一個正方體的6個面涂色，每兩個具有公共棱的面涂成不同的顏色，則不同的涂色方案共有多少種？分析：顯然，至少需要3三種顏色，由于有多種不同情況，仍應(yīng)考慮利用加法原理分類、乘法原理分步進行討論解：根據(jù)共用多少種不同的顏色分類討論（1）用了六種顏色，確定某種顏色所涂面為下底面，則上底顏色可有5種選擇，在上、下底已涂好后，再確定其余4種顏色中的某一種所涂面為左側(cè)面，則其余3個面有3！種涂色方案，根據(jù)乘法原理（2）共用五種顏色，選定五種顏色有種方法，必有兩面同色（必為相對面），確定為上、下底面，其顏色可有5種選擇，再確定一種顏色為左側(cè)面，此時的方法數(shù)取決于右側(cè)面的顏色，有3種選擇（前后面可通過翻轉(zhuǎn)交換）；(3)共用四種顏色,仿上分析可得；(4)共用三種顏色,例10、四棱錐，用4種不同的顏色涂在四棱錐的各個面上，要求相鄰不同色，有多少種涂法？53253214ABCDP解：這種面的涂色問題可轉(zhuǎn)化為區(qū)域涂色問題，如右圖，區(qū)域1、2、3、4相當(dāng)于四個側(cè)面，區(qū)域5相當(dāng)于底面；根據(jù)共用顏色多少分類：最少要用3種顏色，即1與3同色、2與4同色，此時有種；當(dāng)用4種顏色時，1與3同色、2與4兩組中只能有一組同色，此時有；故滿足題意總的涂色方法總方法交總數(shù)為用三種不同的顏色填涂如右圖3方格中的9個區(qū)域，要求每行、每列的三個區(qū)域都不同色，則不同的填涂方法種數(shù)共有（D）A、48、B、24C、12D、6四、染色模型在“立幾”中的計數(shù)問題應(yīng)用在近幾年的高考試題和各地模擬試題中頻繁出現(xiàn)以“立幾”中的點、線、面的位置關(guān)系為背景的計數(shù)問題，這類問題題型新穎、解法靈活、多個知識點交織在一起，綜合性強，能力要求高，有一定的難度，它不僅考查相關(guān)的基礎(chǔ)知識，而且注重對數(shù)學(xué)思想方法和數(shù)學(xué)能力的考查?，F(xiàn)結(jié)合具體例子談?wù)勥@種問題的求解策略。直接求解例1：從平面上取6個點，從平面上取4個點，這10個點最多可以確定多少個三棱錐？解析:利用三棱錐的形成將問題分成平面上有1個點、2個點、3個點三類直接求解共有個三棱錐例2:在四棱錐P-ABCD中，頂點為P，從其它的頂點和各棱的中點中取3個，使它們和點P在同一平面上，不同的取法有A.40B.48C.56D.62種解析:滿足題設(shè)的取法可以分成三類在四棱錐的每一個側(cè)面上除P點外取三點有種不同取法；在兩個對角面上除點P外任取3點，共有種不同取法；過點P的每一條棱上的3點和與這條棱異面的棱的中點也共面，共有種不同取法,故共有40+8+8=56種評注：這類問題應(yīng)根據(jù)立體圖形的幾何特點，選取恰當(dāng)?shù)姆诸悩藴剩龅椒诸惒恢貜?fù)、不遺漏。結(jié)合“立幾”概念求解例3:空間10個點無三點共線，其中有6個點共面，此外沒有任何四個點共面，則這些點可以組成多少個四棱錐？解析:結(jié)合“立幾”圖形求解如果把兩條異面直線看作“一對”，那么六棱錐的棱和底面所有的12條直線中，異面直線有：A.12B.24C.36D.48B用正五棱柱的10個頂點中的5個頂點作四棱錐的5個頂點，共可得多少個四棱錐？分類：以棱柱的底面為棱錐的底面;以棱柱的側(cè)面為棱錐的底面以棱柱的對角面為棱錐的底面以圖中(梯形)為棱錐的底面構(gòu)造幾何模型求解在正方體的8個頂點的所有連線中，有多少對異面直線？與空間不共面的四點距離相等的平面有多少個？（05年湖北）以平面六面體的任意三個頂點為頂點作三角形，從中隨機取出兩個三角形，則這兩個三角形不共面的概率為A.B.C.D.A在知識的網(wǎng)絡(luò)交匯點初設(shè)計命題是近幾年高考命題改革強調(diào)的重要觀念之一，在復(fù)習(xí)備考中，要把握好知識間的縱橫聯(lián)系和綜合，使所學(xué)知識真正融會貫通，運用自如，形成有序的網(wǎng)絡(luò)化知識體系。對于已知直線a,如果直線b同時滿足下列三個條件:①與直線a異面;②與直線a所成的角為定值;③與直線a的距離為定值d.那么這樣的直線b有A.1條B.2條C.3條D.無數(shù)條2.如果一條直線與一個平面垂直,那么稱此直線與平面構(gòu)成一個“正交線面對”.在一個正方體中,由兩個頂點確定的直線與含有四個頂點的平面構(gòu)成的“正交線面對”的個數(shù)是A.48B.36C.24D.183.設(shè)四棱錐P-ABCD的底面不是平行四邊形,用平面去截這個四棱錐,使得截面四邊形是平行四邊形,則這樣的平面A.不存在B.只有1個C.恰有4個D.有無窮多個4.如圖,點分別是四面體的頂點或棱的中點,那么在同一平面上的四點組共有個5.在正方體的一個面所在的平面內(nèi),任意畫一條直線,則與它異面的正方體的棱的條數(shù)是6.正方體的8個頂點中任取4個不在同一平面上的頂點組成的二面角為的大小可能值有個.答案D2.B3.D4.335.4或6或7或86.8個排列組合題型總結(jié)排列組合問題千變?nèi)f化，解法靈活，條件隱晦，思維抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用題時，除做到：排列組合分清，加乘原理辯明，避免重復(fù)遺漏外，還應(yīng)注意積累排列組合問題得以快速準確求解。一．直接法1．特殊元素優(yōu)先法例1用1，2，3，4，5，6這6個數(shù)字組成無重復(fù)的四位數(shù)，試求滿足下列條件的四位數(shù)各有多少個（1）數(shù)字1不排在個位和千位（2）數(shù)字1不在個位，數(shù)字6不在千位。分析：（1）個位和千位有5個數(shù)字可供選擇，其余2位有四個可供選擇，由乘法原理：=2402．特殊位置法（2）當(dāng)1在千位時余下三位有=60，1不在千位時，千位有種選法，個位有種，余下的有，共有=192所以總共有192+60=252二．間接法當(dāng)直接法求解類別比較大時，應(yīng)采用間接法。如上例中（2）可用間接法=252例2有五張卡片，它的正反面分別寫0與1，2與3，4與5，6與7，8與9，將它們?nèi)我馊龔埐⑴欧旁谝黄鸾M成三位數(shù)，共可組成多少個不同的三維書？分析：此例正面求解需考慮0與1卡片用與不用，且用此卡片又分使用0與使用1，類別較復(fù)雜，因而可使用間接計算：任取三張卡片可以組成不同的三位數(shù)個，其中0在百位的有個，這是不合題意的。故共可組成不同的三位數(shù)-=432（個）三．插空法當(dāng)需排元素中有不能相鄰的元素時，宜用插空法。例3在一個含有8個節(jié)目的節(jié)目單中，臨時插入兩個歌唱節(jié)目，且保持原節(jié)目順序，有多少中插入方法？分析：原有的8個節(jié)目中含有9個空檔，插入一個節(jié)目后，空檔變?yōu)?0個，故有=100中插入方法。四．捆綁法當(dāng)需排元素中有必須相鄰的元素時，宜用捆綁法。例44名男生和3名女生共坐一排，男生必須排在一起的坐法有多少種？分析：先將男生捆綁在一起看成一個大元素與女生全排列有種排法，而男生之間又有種排法，又乘法原理滿足條件的排法有：×=576練習(xí)1．四個不同的小球全部放入三個不同的盒子中，若使每個盒子不空，則不同的放法有種（）1．某市植物園要在30天內(nèi)接待20所學(xué)校的學(xué)生參觀，但每天只能安排一所學(xué)校，其中有一所學(xué)校人數(shù)較多，要安排連續(xù)參觀2天，其余只參觀一天，則植物園30天內(nèi)不同的安排方法有（）（注意連續(xù)參觀2天，即需把30天種的連續(xù)兩天捆綁看成一天作為一個整體來選有其余的就是19所學(xué)校選28天進行排列）五．隔板法名額分配或相同物品的分配問題，適宜采隔板用法分析：此例的實質(zhì)是12個名額分配給8個班，每班至少一個名額，可在12個名額種的11個空當(dāng)中插入7塊閘板，一種插法對應(yīng)一種名額的分配方式，故有種練習(xí)1.(a+b+c+d)15有多少項？當(dāng)項中只有一個字母時，有種（即a.b.c.d而指數(shù)只有15故。當(dāng)項中有2個字母時，有而指數(shù)和為15，即將15分配給2個字母時，如何分，閘板法一分為2，即當(dāng)項中有3個字母時指數(shù)15分給3個字母分三組即可當(dāng)項種4個字母都在時四者都相加即可．練習(xí)2．有20個不加區(qū)別的小球放入編號為1，2，3的三個盒子里，要求每個盒子內(nèi)的球數(shù)不少編號數(shù)，問有多少種不同的方法？（）3．不定方程X1+X2+X3+…+X50=100中不同的整數(shù)解有（）六．平均分堆問題例66本不同的書平均分成三堆，有多少種不同的方法？分析：分出三堆書（a1,a2）,(a3,a4)，（a5,a6）由順序不同可以有=6種，而這6種分法只算一種分堆方式，故6本不同的書平均分成三堆方式有=15種練習(xí)：1．6本書分三份，2份1本，1份4本，則有不同分法？2．某年級6個班的數(shù)學(xué)課，分配給甲乙丙三名數(shù)學(xué)教師任教，每人教兩個班，則分派方法的種數(shù)。七．合并單元格解決染色問題例7（全國卷（文、理））如圖1，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有種（以數(shù)字作答）。分析：顏色相同的區(qū)域可能是2、3、4、5．下面分情況討論:(ⅰ)當(dāng)2、4顏色相同且3、5顏色不同時，將2、4合并成一個單元格，此時不同的著色方法相當(dāng)于4個元素①③⑤的全排列數(shù)（ⅱ）當(dāng)2、4顏色不同且3、5顏色相同時，與情形(ⅰ)類似同理可得種著色法．（ⅲ）當(dāng)2、4與3、5分別同色時，將2、4；3、5分別合并，這樣僅有三個單元格①從4種顏色中選3種來著色這三個單元格，計有種方法．由加法原理知：不同著色方法共有2=48+24=72（種）練習(xí)1（天津卷（文））將3種作物種植12345在如圖的5塊試驗田里，每快種植一種作物且相鄰的試驗田不能種植同一作物，不同的種植方法共種（以數(shù)字作答）（72）2．（江蘇、遼寧、天津卷（理））某城市中心廣場建造一個花圃，花圃6分為個部分（如圖3），現(xiàn)要栽種4種顏色的花，每部分栽種一種且相鄰部分不能栽種同一樣顏色的話，不同的栽種方法有種（以數(shù)字作答）．（120）圖3圖43．如圖4，用不同的5種顏色分別為ABCDE五部分著色，相鄰部分不能用同一顏色，但同一種顏色可以反復(fù)使用也可以不用，則符合這種要求的不同著色種數(shù)．（540）4．如圖5：四個區(qū)域坐定4個單位的人，有四種不同顏色的服裝，每個單位的觀眾必須穿同種顏色的服裝，且相鄰兩區(qū)域的顏色不同，不相鄰區(qū)域顏色相同，不相鄰區(qū)域顏色相同與否不受限制，那么不同的著色方法是種（84）圖5圖65．將一四棱錐(圖6)的每個頂點染一種顏色，并使同一條棱的兩端點異色，若只有五種顏色可供使用，則不同