排列組合專題

1、加法原理和乘法原理加法原理和乘法原理 加法原理和乘法原理是排列組合的基礎(chǔ)和核心，既可加法原理和乘法原理是排列組合的基礎(chǔ)和核心，既可用來推導(dǎo)排列數(shù)、組合數(shù)公式，也可用來直接解題。它們用來推導(dǎo)排列數(shù)、組合數(shù)公式，也可用來直接解題。它們的共同點(diǎn)都是把一個事件分成若干個分事件來進(jìn)行計算。的共同點(diǎn)都是把一個事件分成若干個分事件來進(jìn)行計算。 利用加法原理，重在分利用加法原理，重在分“類類”，類與類之間具有獨(dú)立，類與類之間具有獨(dú)立性和并列性；性和并列性； 利用乘法原理，重在分步；步與步之間具有相依性和利用乘法原理，重在分步；步與步之間具有相依性和連續(xù)性。連續(xù)性。 比較復(fù)雜的問題，常先分類再分步。比較復(fù)雜的問

2、題，常先分類再分步。1.加法原理加法原理: 如果完成一項工作有兩類如果完成一項工作有兩類相互獨(dú)立的方式相互獨(dú)立的方式A和和B,在方式在方式A中有中有m種完成任務(wù)的途徑種完成任務(wù)的途徑,在方式在方式B中有中有n種完成任務(wù)的途種完成任務(wù)的途徑徑,則完成這項工作的總的途徑有則完成這項工作的總的途徑有m+n種種.2.乘法原理乘法原理: 如果完成一項工作有兩個如果完成一項工作有兩個連續(xù)的步驟連續(xù)的步驟A和和B,在步驟在步驟A中有中有m種不同的方式種不同的方式,在步驟在步驟B中有中有n種不同的方式種不同的方式,則完成則完成這項工作的總的方法有這項工作的總的方法有m*n種種.例例1、 從從1到到4這這4個數(shù)

3、碼中個數(shù)碼中不重復(fù)地任取不重復(fù)地任取3個構(gòu)成一個構(gòu)成一個三位數(shù)個三位數(shù),求這樣的三位數(shù)一共有多少個求這樣的三位數(shù)一共有多少個?分析分析:構(gòu)成三位數(shù)的過程可以看成是由連續(xù)的三步完成構(gòu)成三位數(shù)的過程可以看成是由連續(xù)的三步完成:第一步第一步:取百位上的數(shù)字取百位上的數(shù)字,共有共有4種方法種方法第二步第二步:取十位上的數(shù)字取十位上的數(shù)字,共有共有3種方法種方法(即不能取百位上已即不能取百位上已經(jīng)取走的數(shù)碼經(jīng)取走的數(shù)碼)第三步第三步:取個位上的數(shù)字取個位上的數(shù)字,共有共有2種方法種方法(即不能取百位和十即不能取百位和十位上已經(jīng)取走的數(shù)碼位上已經(jīng)取走的數(shù)碼)因此由因此由乘法原理乘法原理,這樣的三位數(shù)一共有

4、這樣的三位數(shù)一共有:4*3*2=24種種.例2、 一個三位數(shù)，如果它的每一位數(shù)字都不小于另一一個三位數(shù)，如果它的每一位數(shù)字都不小于另一個三位數(shù)對應(yīng)數(shù)位上的數(shù)字，就稱它個三位數(shù)對應(yīng)數(shù)位上的數(shù)字，就稱它“吃掉吃掉”后一個后一個三位數(shù)，例如三位數(shù)，例如543吃掉吃掉432，543吃掉吃掉543，但是，但是543不能吃掉不能吃掉534。那么能吃掉。那么能吃掉587的三位數(shù)共有多的三位數(shù)共有多少個？少個？ 百位上有百位上有5、6、7、8、9五種選擇，十位上有五種選擇，十位上有8、9兩種選兩種選擇，個位上有擇，個位上有7，8，9三種選擇，所以共有三種選擇，所以共有523=30（個）（個）三位數(shù)。三位數(shù)。例

5、例3、 如圖，一方形花壇分成編號為如圖，一方形花壇分成編號為，四塊，現(xiàn)四塊，現(xiàn)有紅、黃、藍(lán)、紫四種顏色的花供選種，要求每塊只種一種有紅、黃、藍(lán)、紫四種顏色的花供選種，要求每塊只種一種顏色的花，且相鄰的兩塊種不同顏色的花。顏色的花，且相鄰的兩塊種不同顏色的花。如果編號為如果編號為的的已經(jīng)種上紅色花已經(jīng)種上紅色花，那么其余三塊不同的種法有，那么其余三塊不同的種法有 種。種。21 編號為編號為的有三種選擇，對于編號為的有三種選擇，對于編號為的，可以分成以下二類：的，可以分成以下二類：1、若編號為若編號為的與編號為的與編號為的同色的同色，則編，則編號為號為的有三種選擇。這種情況下共有的有三種選擇。這種

6、情況下共有33種方案。種方案。2、若編號為若編號為的與編號為的與編號為的不同色的不同色，則，則編號為編號為的有二種選擇，編號為的有二種選擇，編號為的有二種的有二種選擇。這種情況下共有選擇。這種情況下共有322種方案。種方案。例例4、 用紅、黃、綠、藍(lán)、黑五種顏色涂在如用紅、黃、綠、藍(lán)、黑五種顏色涂在如下圖所示的下圖所示的ABCDE五區(qū)域，顏色可重復(fù)使用，五區(qū)域，顏色可重復(fù)使用，但同色不相鄰，涂法有幾種？但同色不相鄰，涂法有幾種？ AC同色同色:5*4*4*1*4AC不同色不同色:5*4*4*3*31040 例例5、 在一塊并排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟，為有利

7、于作物生長，要求A，B兩種作物的間隔不少于6壟，不同的選法共有_種。分析：采取分類的方法。 第一類：A在第一壟，B有3種選擇；第二類：A在第二壟，B有2種選擇； 第三類：A在第三壟，B有一種選擇， 同理A、B位置互換 ，共12種。 例例6、 某小組有某小組有10人，每人至少會英語和日語的一門，人，每人至少會英語和日語的一門，其中其中8人會英語，人會英語，5人會日語，從中選出會英語與會人會日語，從中選出會英語與會日語的各日語的各1人，有多少種不同的選法人，有多少種不同的選法? 由于由于8+51310，所以，所以10人中必有人中必有3人既會英人既會英語又會日語。語又會日語。（5+2+3）所以可分三

8、類：所以可分三類： 52 + 53 + 23=31例例7、 在所有的三位數(shù)中，有且只有兩個數(shù)字相同在所有的三位數(shù)中，有且只有兩個數(shù)字相同的三位數(shù)共有多少個的三位數(shù)共有多少個? （1），（2），（3），（1），（），（2 ），（），（3）類中每類都是）類中每類都是99種，共有種，共有99+99+99399243個只有兩個數(shù)字相同的個只有兩個數(shù)字相同的三位數(shù)。三位數(shù)。 例例8、求正整數(shù)求正整數(shù)1400的正因數(shù)的個的正因數(shù)的個數(shù)數(shù) 因為因為任何一個正整數(shù)的任何一個正因數(shù)任何一個正整數(shù)的任何一個正因數(shù)(除除1外外)都是這個都是這個數(shù)的一些質(zhì)因數(shù)的積數(shù)的一些質(zhì)因數(shù)的積，因此，我們先把，因此，我們先把14

9、00分解成質(zhì)因數(shù)的分解成質(zhì)因數(shù)的連乘積連乘積1400=23527.所以這個數(shù)的任何一個正因數(shù)都是由所以這個數(shù)的任何一個正因數(shù)都是由2，5，7中的中的若干若干個相乘而得到個相乘而得到(有的可重復(fù)有的可重復(fù))。 于是取于是取1400的一個正因數(shù)，這件事情是分如下三個步驟的一個正因數(shù)，這件事情是分如下三個步驟完成的：完成的：(1)取取23的正因數(shù)是的正因數(shù)是20，21，22，23，共，共3+1種；種；(2)取取52的正因數(shù)是的正因數(shù)是50，51，52，共，共2+1種；種；(3)取取7的正因數(shù)是的正因數(shù)是70，71，共，共1+1種種所以所以1400的正因數(shù)個數(shù)為的正因數(shù)個數(shù)為(3+1)(2+1)(1+

10、1)=24例例9、 從從1到到300的自然數(shù)中，完全不含有數(shù)字的自然數(shù)中，完全不含有數(shù)字3的的有多少個？有多少個？ 將將0到到299的整數(shù)都看成三位數(shù)，其中數(shù)字的整數(shù)都看成三位數(shù)，其中數(shù)字3不不出現(xiàn)的，百位數(shù)字可以是出現(xiàn)的，百位數(shù)字可以是0，1或或2三種情況。十位三種情況。十位數(shù)字與個位數(shù)字均有九種，因此數(shù)字與個位數(shù)字均有九種，因此除去除去0共有共有3991=242(個個)例例10、 在小于在小于10000的自然數(shù)中，含有數(shù)字的自然數(shù)中，含有數(shù)字1的數(shù)有的數(shù)有多少個？多少個？ 不妨將不妨將0至至9999的自然數(shù)均看作四位數(shù)，凡位數(shù)不到的自然數(shù)均看作四位數(shù)，凡位數(shù)不到四位的自然數(shù)在前面補(bǔ)四位的自

11、然數(shù)在前面補(bǔ)0, ,使之成為四位數(shù)。使之成為四位數(shù)。先求不含數(shù)字先求不含數(shù)字1的這樣的四位數(shù)共有幾個，即有的這樣的四位數(shù)共有幾個，即有0，2，3，4，5，6，7，8，9這九個數(shù)字所組成的四位數(shù)的個數(shù)。這九個數(shù)字所組成的四位數(shù)的個數(shù)。由于每一位都可有由于每一位都可有9種寫法，所以，根據(jù)乘法原理，由這九種寫法，所以，根據(jù)乘法原理，由這九個數(shù)字組成的四位數(shù)個數(shù)為個數(shù)字組成的四位數(shù)個數(shù)為99996561。 于是，小于于是，小于10000且含有數(shù)字且含有數(shù)字1的自然數(shù)共有的自然數(shù)共有9999-6561=3438個個排列的定義排列的定義 數(shù)學(xué)上，把若干元素，按照任何一種順序排成數(shù)學(xué)上，把若干元素，按照任何

12、一種順序排成一列，叫做排列。一列，叫做排列。 如果兩個排列滿足下列條件之一，它們就被認(rèn)如果兩個排列滿足下列條件之一，它們就被認(rèn)為是不同的排列：為是不同的排列： 1.所含元素不全相同所含元素不全相同 2.所含元素相同，但順序不同。所含元素相同，但順序不同。相異元素不重復(fù)的排列相異元素不重復(fù)的排列 從從 n個不同的元素中，取出個不同的元素中，取出r個不重復(fù)的元素，個不重復(fù)的元素，按次序排成一列，當(dāng)按次序排成一列，當(dāng)rn時，稱為從時，稱為從n個中取個中取r個的個的一種選排列。一種選排列。如：從如：從a,b,c這三個字母中，每次取出這三個字母中，每次取出2個，有多少種排列方法個，有多少種排列方法?第一

13、步：確定左邊的字母，在三個字母中任取一個，有種方法；第一步：確定左邊的字母，在三個字母中任取一個，有種方法；第二步：確定右邊的字母，從剩下的個字母中選取一個，有種第二步：確定右邊的字母，從剩下的個字母中選取一個，有種方法；方法；根據(jù)根據(jù)乘法原理乘法原理，共有，共有種不同的排法種不同的排法. ab ac ba bc ca cb 一般地，從一般地，從n個不同的元素中取出個不同的元素中取出r個元素的個元素的選排列數(shù)用選排列數(shù)用 表示，則表示，則 n!/(n-r)!rnPrnP例例全國足球甲級（組）聯(lián)賽共有隊參全國足球甲級（組）聯(lián)賽共有隊參加，每隊都要與其它各隊在加，每隊都要與其它各隊在主、客場主、客

14、場分別比賽一分別比賽一次，共進(jìn)行多少場比賽？次，共進(jìn)行多少場比賽？ 任何二個隊進(jìn)行一次主場比賽和一場客場比任何二個隊進(jìn)行一次主場比賽和一場客場比賽，相當(dāng)于從賽，相當(dāng)于從14個元素中任取個元素中任取2個元素的一個排個元素的一個排列，共需進(jìn)行的比賽場次是列，共需進(jìn)行的比賽場次是 =14!/12!=14*13=182214P當(dāng)當(dāng)n=r時時,叫做叫做n個不同元素的個不同元素的全排列全排列n個不同元素的全排列數(shù)個不同元素的全排列數(shù)Pnn n!例例個人站成一排照相，共有多少種不同的排個人站成一排照相，共有多少種不同的排列方法？列方法？ !33P例例3、求有多少個、求有多少個沒有重復(fù)數(shù)字沒有重復(fù)數(shù)字且能被且

15、能被5整除整除的四位奇數(shù)。的四位奇數(shù)。 要能被要能被5整除又是奇數(shù)，所以個位上數(shù)字只能整除又是奇數(shù)，所以個位上數(shù)字只能是是5,有有1種選法，由于種選法，由于5已用過，又不可能是已用過，又不可能是0,所以所以千位上數(shù)有千位上數(shù)有P18種選法種選法,已用過已用過2個數(shù)，所以百位、十個數(shù)，所以百位、十位上的數(shù)有位上的數(shù)有P28種選法。種選法。 所以符合題意的個數(shù)為：所以符合題意的個數(shù)為： 1 P18 P28448例例4、用、用0、1、2、3、4、5六個數(shù)字，可以六個數(shù)字，可以組成多少個沒有重復(fù)數(shù)字的三位偶數(shù)？組成多少個沒有重復(fù)數(shù)字的三位偶數(shù)？1.個位為個位為0,十位為十位為1、2、3、4、5中的一個

16、，百位為剩下的中的一個，百位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有四個數(shù)字中的一個，所以這樣的偶數(shù)共有1P15P142.個位為個位為2,百位為百位為1、3、4、5中的一個，十位為剩下的四個中的一個，十位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有數(shù)字中的一個，所以這樣的偶數(shù)共有1P14P143.個位為個位為4,百位為百位為1、2、3、5中的一個，十位為剩下的四個中的一個，十位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有數(shù)字中的一個，所以這樣的偶數(shù)共有1P14P14所以符合題意的個數(shù)為所以符合題意的個數(shù)為20161652例例5、 8位同學(xué)排成相等的兩行，要求某兩位同位同學(xué)排成相等的兩行，要

17、求某兩位同學(xué)必須排在前排，有多少種排法？學(xué)必須排在前排，有多少種排法？ 這兩個同學(xué)排在前排這兩個同學(xué)排在前排4個位置的排列數(shù)是個位置的排列數(shù)是P24，其它同學(xué)在余下的其它同學(xué)在余下的6個位置排的排列數(shù)是個位置排的排列數(shù)是6！，所！，所以符合題意的個數(shù)為以符合題意的個數(shù)為P246！127208640。例例6、某車站有編號為某車站有編號為1到到6的的6個入口處，每個個入口處，每個入口處入口處每次只能進(jìn)一人每次只能進(jìn)一人，問一個小組，問一個小組4人進(jìn)站的人進(jìn)站的方案有幾種？方案有幾種？第一個人有第一個人有6種方案，第二個人有種方案，第二個人有7種方案，因為種方案，因為他選擇和第一個人相同入口處時，還

18、有前后之他選擇和第一個人相同入口處時，還有前后之分分9*8*7*6=3024 o o oo 在兩個入口之間加一個標(biāo)志，在兩個入口之間加一個標(biāo)志，共共5個無區(qū)別的標(biāo)志，問題歸結(jié)為個無區(qū)別的標(biāo)志，問題歸結(jié)為9個元素中有個元素中有5個無個無區(qū)別的元素，區(qū)別的元素，4個不同元素的排列數(shù)。所以個不同元素的排列數(shù)。所以4個人進(jìn)站個人進(jìn)站的方案數(shù)有：的方案數(shù)有：9！/5！9*8*7*6=3024相異元素的可重復(fù)排列相異元素的可重復(fù)排列 從從n個不同元素中取出個不同元素中取出r個元素的可重復(fù)的排列個元素的可重復(fù)的排列種數(shù)為種數(shù)為nr.93=729例例7由數(shù)字由數(shù)字1,2,3,9共能組成多少個三位數(shù)？共能組成多

19、少個三位數(shù)？相異元素的循環(huán)排列相異元素的循環(huán)排列 n個不同元素不分首尾排成一個圓圈，稱為循環(huán)個不同元素不分首尾排成一個圓圈，稱為循環(huán)排列。其排列數(shù)為排列。其排列數(shù)為n!/n=(n-1)!。 如如1,2,3三個數(shù)的循環(huán)排列只有，三個數(shù)的循環(huán)排列只有，二種。二種。例例8在圓形花壇外側(cè)擺放盆菊花和盆蘭花，在圓形花壇外側(cè)擺放盆菊花和盆蘭花，要求蘭花不能相鄰擺放，一共有多少種擺法？要求蘭花不能相鄰擺放，一共有多少種擺法？盆菊花擺成一周的排列方法有盆菊花擺成一周的排列方法有n1=！盆蘭花插入個空中的排列總數(shù)有盆蘭花插入個空中的排列總數(shù)有n2=P=8!/4!擺放總數(shù)為擺放總數(shù)為n=n1*n2=8467200

20、例例9有男女各五個人，其中有對是夫妻，沿有男女各五個人，其中有對是夫妻，沿圓桌就座，若每對夫妻都坐在相鄰的位置，問有圓桌就座，若每對夫妻都坐在相鄰的位置，問有多少種坐法？多少種坐法？設(shè)對夫妻分別為和設(shè)對夫妻分別為和a,和和b,和和c，先讓，先讓，三人和另外個人沿圓桌就座的方法為！種三人和另外個人沿圓桌就座的方法為！種又對上述每種坐法，又對上述每種坐法，a坐在的鄰座的方式有左右兩坐在的鄰座的方式有左右兩種，種，b,c也如此也如此所以共有！種所以共有！種不全相異元素的排列不全相異元素的排列 如果在如果在n個元素中，有個元素中，有n1個元素彼此相同，有個元素彼此相同，有n2個元素彼此相同，個元素彼此

21、相同，,又有又有nm個元素彼此相同，若個元素彼此相同，若n1+n2+nm=n，則這，則這n個元素的全排列叫做個元素的全排列叫做不全不全相異元素的全排列相異元素的全排列，其排列數(shù)為，其排列數(shù)為: n!/(n1!*n2!*nm!). 若若n1+n2+nm=rn，則這，則這n個元素的全排個元素的全排列叫做列叫做不全相異元素的選排列不全相異元素的選排列，其排列數(shù)為，其排列數(shù)為: prn/(n1!*n2!*nm!).例例10、將將N個紅球和個紅球和M個黃球排成一行。如個黃球排成一行。如:N=2,M=3可得到可得到10種排法。問題種排法。問題:當(dāng)當(dāng)N=4,M=3時有時有 種不同種不同排法排法?7!/(4!

22、*3!)=35NOIP2002 例例11、把兩個紅球、一個藍(lán)球和一個白球放到、把兩個紅球、一個藍(lán)球和一個白球放到十個編號不同的盒子中去，有多少種方法？十個編號不同的盒子中去，有多少種方法？排列數(shù)為排列數(shù)為p410/(2!*1!*1!)2520生成排列的算法生成排列的算法 下面程序的功能是利用遞歸方法生成從下面程序的功能是利用遞歸方法生成從1到到n(n10)的的n個數(shù)的全部可能的排列（不一定按升個數(shù)的全部可能的排列（不一定按升序輸出）。序輸出）。 例如，輸入例如，輸入3，則應(yīng)該輸出（每行輸出，則應(yīng)該輸出（每行輸出5個排個排列）：列）： 123 132 213 231 321 312 求全排列求全

23、排列(06年初賽題年初賽題)var var i i,n,k:integer; ,n,k:integer; a a:array1.10 of integer; :array1.10 of integer; count:longint count:longint; ; procedure perm(procedure perm( k k:integer); :integer); var var j,p,t:integer; j,p,t:integer; begin begin if( )then if( )then begin begin ( ); ( ); for p:=1 to k do fo

24、r p:=1 to k do write(ap:1); write(ap:1); write( ); write( ); if( )then if( )then writeln writeln; ; exit; exit; end; end; for j:=k to n do for j:=k to n do begin begin t:=ak; t:=ak; ak ak:=aj; :=aj; aj aj:=t;:=t; perm(k+1) perm(k+1) ; ; t:=ak;( ) t:=ak;( ) end end end; end; begin begin writeln(Entry

25、 writeln(Entry n:); n:); read(n); read(n); count:=0; count:=0; for i:=1 to n do ai:=i; for i:=1 to n do ai:=i; ( ) ( ) end.end.perm(1)K=ninc(count)count mod 5=0ak:=aj; aj:=t ;123 132 213 231 321 312算法過程算法過程:用數(shù)組：用數(shù)組：a:array1.r of integer ;表示排列表示排列; 初始化時，初始化時，ai:=i(i=1,2,r);設(shè)中間的某一個排列為設(shè)中間的某一個排列為a1,a2,，

26、ar，則求出下一個排列的算法為：，則求出下一個排列的算法為：從后面向前找，直到找到一個順序為止從后面向前找，直到找到一個順序為止（設(shè)下標(biāo)為（設(shè)下標(biāo)為j-1,則則aj-1aj）從從aj ar中，找出一個比中，找出一個比aj-1大的最小元素大的最小元素ak將將aj-1與與ak交換交換將將aj，aj+1ar由小到大排序。由小到大排序。 問題描述問題描述: 用生成法求出用生成法求出1，2，r的全排列的全排列(raj(ai1aj-1)and(ai1ak1 3 2 5 41 3 4 5 21 3 4 2 5【問題描述【問題描述】 人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人人類終于登上了火

27、星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。都無法理解對方的語言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個非常大的數(shù)字告訴人類科學(xué)這種交流方法是這樣的，首先，火星人把一個非常大的數(shù)字告訴人類科學(xué)家，科學(xué)家破解這個數(shù)字的含義后，再把一個很小的數(shù)字加到這個大數(shù)上家，科學(xué)家破解這個數(shù)字的含義后，再把一個很小的數(shù)字加到這個大數(shù)上面，把結(jié)果告訴火星人，作為人類的回答。面，把結(jié)果告訴火星人，作為人類的回答。 火星人用一種非常簡單的方式來表示數(shù)字火星人用一種非常簡單的方式來表示數(shù)字掰手指。火星人只有

28、一掰手指?；鹦侨酥挥幸恢皇?，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為1，2，3。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方?；鹦侨说娜我鈨筛种付寄茈S意交換位置，他們就是通過這方法計數(shù)的。一個火星人用一個人類的手演示了如何用手指計數(shù)。如果把五法計數(shù)的。一個火星人用一個人類的手演示了如何用手指計數(shù)。如果把五根手指根手指拇指、食指、中指、無名指和小指分別編號為拇指、食指、中指、無名指和小指分別編號為1，2，3，4和和5，當(dāng)它們按正常順序排列時，形成了當(dāng)它們按正常順序排列時，形成了5位數(shù)位數(shù)12345，當(dāng)你交換

29、無名指和小指的，當(dāng)你交換無名指和小指的位置時，會形成位置時，會形成5位數(shù)位數(shù)12354，當(dāng)你把五個手指的順序完全顛倒時，會形成，當(dāng)你把五個手指的順序完全顛倒時，會形成54321，在所有能夠形成的，在所有能夠形成的120個個5位數(shù)中，位數(shù)中，12345最小，它表示最小，它表示1；12354第二小，它表示第二小，它表示2；54321最大，它表示最大，它表示120。下表展示了只有。下表展示了只有3根根手指時能夠形成的手指時能夠形成的6個個3位數(shù)和它們代表的數(shù)字：位數(shù)和它們代表的數(shù)字：三進(jìn)制數(shù)三進(jìn)制數(shù)123132213231312321代表的數(shù)字代表的數(shù)字123456火星人（火星人（04年普及組）年普

30、及組） 現(xiàn)在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看現(xiàn)在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學(xué)家會告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用他的手指，科學(xué)家會告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個結(jié)果不會超出火星人手指能表示的范圍。的排列順序。輸入數(shù)據(jù)保證這個結(jié)果不會超出火星人手指能表示的范圍。【輸入文件【輸入文件】輸入文件輸入文件martian.in包括三行，第一行有

31、一個正整數(shù)包括三行，第一行有一個正整數(shù)N，表示火星人手指的，表示火星人手指的數(shù)目（數(shù)目（1 = N = 10000）。第二行是一個正整數(shù)）。第二行是一個正整數(shù)M，表示要加上去的小，表示要加上去的小整數(shù)（整數(shù)（1 = M = 100）。下一行是）。下一行是1到到N這這N個整數(shù)的一個排列，用空格個整數(shù)的一個排列，用空格隔開，表示火星人手指的排列順序。隔開，表示火星人手指的排列順序?！据敵鑫募据敵鑫募枯敵鑫募敵鑫募artian.out只有一行，這一行含有只有一行，這一行含有N個整數(shù)，表示改變后的火星人個整數(shù)，表示改變后的火星人手指的排列順序。每兩個相鄰的數(shù)中間用一個空格分開，不能有多余的空格

32、。手指的排列順序。每兩個相鄰的數(shù)中間用一個空格分開，不能有多余的空格?！緲永斎搿緲永斎搿?31 2 3 4 5【樣例輸出【樣例輸出】1 2 4 5 3【數(shù)據(jù)規(guī)模【數(shù)據(jù)規(guī)?！繉τ趯τ?0%的數(shù)據(jù)，的數(shù)據(jù)，N=15；對于對于60%的數(shù)據(jù)，的數(shù)據(jù)，N=50；對于全部的數(shù)據(jù)，對于全部的數(shù)據(jù)，N0 do一次循環(huán)產(chǎn)生下一個排列一次循環(huán)產(chǎn)生下一個排列 begin j:=n; while (j1)and(ajaj-1 min:=aj; k:=j; for i:=j to n do if (aiaj-1)and(aiak then ss:=k; if ssi then begin temp:=ai; ai:

33、=ass; ass:=temp; end; end; 在在j到到n中，從小到大排列中，從小到大排列 m:=m-1; end; for i:=1 to n do write(ai, );end.531 2 3 4 51 2 3 5 4 1 2 4 5 3 1 2 4 3 51 2 4 5 3 組合的定義組合的定義 數(shù)學(xué)上，把若干元素，不論次序并成一組，數(shù)學(xué)上，把若干元素，不論次序并成一組，叫做組合。叫做組合。 如果兩個組合中，至少有一個元素不同，如果兩個組合中，至少有一個元素不同，它們就被認(rèn)為是不同的組合。它們就被認(rèn)為是不同的組合。abc,abd相異元素不重復(fù)的組合相異元素不重復(fù)的組合 設(shè)從設(shè)從

34、n個不同的元素中，取出個不同的元素中，取出m個不同元素，個不同元素，不考慮不考慮順序順序并成一組，叫作從并成一組，叫作從n個不同的元素中，取出個不同的元素中，取出m個不同個不同元素的一個組合。元素的一個組合。如：寫出從如：寫出從a,b,c,d四個元素中，任取三個元素的所有組合。四個元素中，任取三個元素的所有組合。abc, abd, acd, bcd從從n個不同的元素中，取出個不同的元素中，取出m個不同元素的組合數(shù)記為個不同元素的組合數(shù)記為Cmn;則有則有CmnPmn/m!=n!/m!(n-m)!規(guī)定規(guī)定C0n=1abc,bac,cab,acb,bca,cba例例1、八年級八年級6個班進(jìn)行排球比

35、賽，每班的排球隊個班進(jìn)行排球比賽，每班的排球隊要與其他要與其他5個班分別比賽一場，求共要進(jìn)行多少場個班分別比賽一場，求共要進(jìn)行多少場比賽？比賽？C26P26/2!=6*5/2*1=15例例2、平面上有平面上有n個點(diǎn)且無三點(diǎn)或三點(diǎn)以上共線，任個點(diǎn)且無三點(diǎn)或三點(diǎn)以上共線，任意兩點(diǎn)可以連成一條直線，一共能連成多少條直線？意兩點(diǎn)可以連成一條直線，一共能連成多少條直線？ C2nn*(n-1)/2例例3、某班第一組有、某班第一組有10名同學(xué)，第二組有名同學(xué)，第二組有8名同學(xué)，現(xiàn)要求每名同學(xué)，現(xiàn)要求每組選出組選出2名學(xué)生代表參加座談會，有多少種選法？名學(xué)生代表參加座談會，有多少種選法？C210C281260

36、例例4.一元、二元、五元、十元人民幣各一張，一共一元、二元、五元、十元人民幣各一張，一共可以組成多少種不同的幣值？可以組成多少種不同的幣值？ C14C24C34C44464115例例5、5年級有年級有8個班，六年級有個班，六年級有6個班，先分別舉行各年個班，先分別舉行各年級的籃球賽，采用單循環(huán)制，然后由兩個年級的第一名爭級的籃球賽，采用單循環(huán)制，然后由兩個年級的第一名爭奪冠軍，共需要比賽多少場？奪冠軍，共需要比賽多少場？ C28C26+1=8*7/2+6*5/2+1=28+15+1=44例例6：某班第一組有：某班第一組有10名同學(xué)，其中有名同學(xué)，其中有4名女同學(xué)，現(xiàn)要名女同學(xué)，現(xiàn)要求選出求選出

37、3名學(xué)生代表名學(xué)生代表,其中至少有一名女同學(xué)去參加座談其中至少有一名女同學(xué)去參加座談會，有多少種選法？會，有多少種選法？ 代表中有代表中有1名女同學(xué)名女同學(xué)的選法為的選法為C14C26種，種， 代表中有代表中有2名女同學(xué)名女同學(xué)的選法為的選法為C24C16種，種， 代表中有代表中有3名女同學(xué)名女同學(xué)的選法為的選法為C34種，種，C14C26C24C16C34100例例7 7、欲登上第欲登上第1010級樓梯，如果規(guī)定每步只能跨級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有上一級或兩級，則不同的走法共有( )( )。 例例8、A的一邊的一邊AB上有上有4個點(diǎn)，另一邊個點(diǎn)，另一邊AC上有上

38、有5個點(diǎn)，個點(diǎn)，連同連同A的頂點(diǎn)共的頂點(diǎn)共10個點(diǎn)，以這些點(diǎn)為頂點(diǎn)，可以構(gòu)個點(diǎn)，以這些點(diǎn)為頂點(diǎn)，可以構(gòu)成成_個三角形個三角形. 9090541452524CC例例9、平面上有三條平行直線，每條直線上分別有平面上有三條平行直線，每條直線上分別有7，5，6個點(diǎn)，且不同直線上三個點(diǎn)都不在同一條直線上。問用個點(diǎn)，且不同直線上三個點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個不同三角形？（這些點(diǎn)為頂點(diǎn)，能組成多少個不同三角形？（2001年年p）C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180

39、+210=751例例10、平面上有三條平行直線，每條直線上分別有平面上有三條平行直線，每條直線上分別有7，5，6個點(diǎn)，且不同直線上三個點(diǎn)都不在同一條直線上。問用個點(diǎn)，且不同直線上三個點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個不同四邊形這些點(diǎn)為頂點(diǎn)，能組成多少個不同四邊形?（2001年年t）C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+ C(7,2)*5*6+ C(5,2)*7*6+ C(6,2)*5*7=21*10+21*15+10*15+21*5*6+10*7*6+15*5*7=2250 例例11、10名劃船運(yùn)動員中，名劃船運(yùn)動員中，3人只會劃

40、左舷，人只會劃左舷，2人只會劃人只會劃右舷，右舷，5人左右舷都會劃，從中選人左右舷都會劃，從中選6人，平均分在左、右人，平均分在左、右舷，共有多少種不同的選法？舷，共有多少種不同的選法？ 1.會劃左舷的全劃左舷：會劃左舷的全劃左舷：35*3733CC300*362315CCC40*3435CC2.派一個全能劃左舷：派一個全能劃左舷：3.派二個全能劃左舷：派二個全能劃左舷：4.派三個全能劃左舷：派三個全能劃左舷：300*351325CCC675例例12、小陳現(xiàn)有小陳現(xiàn)有2個任務(wù)個任務(wù)A，B要完成，每個任務(wù)分別要完成，每個任務(wù)分別有若干步驟如下：有若干步驟如下：A=a1-a2-a3，B=b1-b2

41、-b3-b4-b5。在任何時候，小陳只能專心做某個任務(wù)的。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一當(dāng)前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如例如a2-b2-a3-b3是合法的，而是合法的，而a2-b3-a3-b2是不合法的。小陳從是不合法的。小陳從B任務(wù)的任務(wù)的b1步步驟開始做，當(dāng)恰做完某個任務(wù)的某個步驟后，就停工驟開始做，當(dāng)恰做完某個任務(wù)的某個步驟后，就停工回家

42、吃飯了。當(dāng)他回來時，只記得自己已經(jīng)完成了整回家吃飯了。當(dāng)他回來時，只記得自己已經(jīng)完成了整個任務(wù)個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可，其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有能的任務(wù)步驟序列共有 種。種。(2009年年p) 70 排列組合排列組合+加法原理加法原理:B任務(wù)中的任務(wù)中的b1一定做，而且肯定是第一個做的。除了一定做，而且肯定是第一個做的。除了b1外，外，第一類：完成第一類：完成A任務(wù)任務(wù) 只有只有1種。種。第二類：完成第二類：完成A任務(wù)和任務(wù)和b2 有有C(4,1)=4種。種。第三類：完成第三類：完成A任務(wù)和任務(wù)和b2、b3 有有C(5,2)=10種。種。第

43、四類：完成第四類：完成A任務(wù)和任務(wù)和b2、b3、b4 有有C(6,3)=20種。種。第五類：完成第五類：完成A任務(wù)和任務(wù)和b2、b3、b4、b5 有有C(7,4)=35種。種。加起來加起來1+4+10+20+35=70。b2 a1 a2 a3a1 b2 a2 a3a1 a2 b2 a3a1 a2 a3 b2 例例13、袋中有已編號的袋中有已編號的20個球，其中個球，其中110號是紅球，號是紅球，1120號是白球，每取得一個紅球得號是白球，每取得一個紅球得2分，取得一個分，取得一個白球得白球得3分，若取得若干個球，共得分，若取得若干個球，共得20分，有多少種分，有多少種不同取法？不同取法？2x+

44、3y=20, y必是偶數(shù)，必是偶數(shù)，所以所以y=0,2,4,6；相應(yīng)地；相應(yīng)地x=10,7,4,1； C010C1010C210C710 C410C410 C610C110 51601例例14、從從1300之間任取之間任取3個不同的數(shù)，使得這個不同的數(shù)，使得這3個數(shù)個數(shù)的和恰好被的和恰好被3除盡，有多少種方法？除盡，有多少種方法？ 被被3除所得的余數(shù)不外乎：除所得的余數(shù)不外乎：0，1，2。所以可把。所以可把1300之之間的數(shù)分成三組：間的數(shù)分成三組： A1,4,7,298 B2,5,8,299 C3,6,9,300 三個數(shù)同屬于集合三個數(shù)同屬于集合A，有，有C3100種，種， 三個數(shù)同屬于集合

45、三個數(shù)同屬于集合B，有，有C3100種，種， 三個數(shù)同屬于集合三個數(shù)同屬于集合C，有，有C3100種，種， 三個數(shù)分屬于集合三個數(shù)分屬于集合A，B，C，有，有1003種。加起來等于種。加起來等于 1485100種。種。例例15、若將一個正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，若將一個正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字我們將數(shù)字0的個數(shù)多于數(shù)字的個數(shù)多于數(shù)字1的個數(shù)的這類二進(jìn)制數(shù)稱為的個數(shù)的這類二進(jìn)制數(shù)稱為A類數(shù)。類數(shù)。 例如：例如： （24）10=（11000）2 其中其中1的個數(shù)為的個數(shù)為2，0的個數(shù)為的個數(shù)為3，則稱此數(shù)為，則稱此數(shù)為A類數(shù)；類數(shù)； 請你求出請你求出1112之中（包

46、括之中（包括1與與112），全部），全部A類數(shù)類數(shù)的個數(shù)。的個數(shù)。 （112）10=（1110000）2可根據(jù)二進(jìn)制數(shù)的前綴來分類?？筛鶕?jù)二進(jìn)制數(shù)的前綴來分類。111：這類數(shù)中：這類數(shù)中A類數(shù)只有一個，即類數(shù)只有一個，即1110000110：這類數(shù)中：這類數(shù)中A類數(shù)個數(shù)為：類數(shù)個數(shù)為： C44C34510：這類數(shù)中：這類數(shù)中A類數(shù)個數(shù)為：類數(shù)個數(shù)為： C55C45 C35 160：位數(shù)不確定，需對位數(shù)進(jìn)行討論。：位數(shù)不確定，需對位數(shù)進(jìn)行討論。1位數(shù)，即位數(shù)，即1,不是不是A類數(shù)，類數(shù)，2位數(shù)，即位數(shù)，即1，10和和11都不是都不是A類數(shù)，類數(shù)，3位數(shù)，即位數(shù)，即1，只有，只有100一個，一個，

47、4位數(shù)，即位數(shù)，即1，只有，只有1000一個，一個，5位數(shù)，即位數(shù)，即1， A類數(shù)個數(shù)有類數(shù)個數(shù)有C44C345,6位數(shù)，即位數(shù)，即1， A類數(shù)個數(shù)有類數(shù)個數(shù)有C55C456,1516（1156）35例16、 某城市有4條東西街道和6條南北的街道，街道之間的間距相同。若規(guī)定只能向東或向北兩個方向沿圖中路線前進(jìn)，則從M到N有多少種不同的走法?(2007年p) MN（一）從M到N必須向上走三步，向右走五步，共走八步。 （二）每一步是向上還是向右，決定了不同的走法。 （三）事實上，當(dāng)把向上的步驟決定后，剩下的步驟只能向右。 從而，任務(wù)可敘述為：從八個步驟中選出哪三步是向上走，就可以確定走法數(shù)。 本題

48、答案為56。 相異元素的可重復(fù)組合相異元素的可重復(fù)組合 設(shè)從設(shè)從n個不同的元素中，取出個不同的元素中，取出m個不同元素，個不同元素，若允許這個元若允許這個元素可以重復(fù)使用素可以重復(fù)使用，也允許，也允許mn，則把這樣的組合稱為重復(fù)組合，則把這樣的組合稱為重復(fù)組合，其組合數(shù)記為其組合數(shù)記為Hmn。 Hmn=Cmn+m-1 如如1,2,3,4,四個數(shù)字中取三個，允許重復(fù)的組合有以下四個數(shù)字中取三個，允許重復(fù)的組合有以下20種：種： 111, 122, 134, 224, 333 112, 123, 144, 233, 334 113, 124, 222, 234, 344 114, 133, 223

49、, 244, 444組合的生成算法組合的生成算法 從1,2,3,n共n個數(shù)中任取m個數(shù)，請輸出所有組合并計算組合數(shù)。var n,m,i,k,s:integer; a,b:array0.100 of integer;begin readln(n,m); for i:=1 to m do begin ai:=i; bi:= ; end; k:=m; s:=0; repeat if then begin s:=s+1; for i:=1 to m do write(ai); write( ); end; if akbk then begin ; if km then for k:=k+1 to m

50、do ; end else ; until k=0; writeln; writeln(s=,s);end. n-m+ik=mak:=ak+1ak:=ak-1+1k:=k-1Jam的計數(shù)法的計數(shù)法【問題描述【問題描述】 Jam是個喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計數(shù)，而是個喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計數(shù)，而是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），英文字母按原先的順

51、序，排在前面的字母小于排在它后面的字母。我們英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的把這樣的“數(shù)字?jǐn)?shù)字”稱為稱為Jam數(shù)字。在數(shù)字。在Jam數(shù)字中，每個字母互不相同，數(shù)字中，每個字母互不相同，而且從左到右是嚴(yán)格遞增的。每次，而且從左到右是嚴(yán)格遞增的。每次，Jam還指定使用字母的范圍，例如，還指定使用字母的范圍，例如，從從2到到10，表示只能使用，表示只能使用b,c,d,e,f,g,h,i,j這些字母。如果再規(guī)定位這些字母。如果再規(guī)定位數(shù)為數(shù)為5，那么，緊接在，那么，緊接在Jam數(shù)字?jǐn)?shù)字“bdfij”之后的數(shù)字應(yīng)該是之后的數(shù)字應(yīng)該是“bdghi”。（如果我們用（如果

52、我們用U、V依次表示依次表示Jam數(shù)字?jǐn)?shù)字“bdfij”與與“bdghi”，則，則UV，且不存在且不存在Jam數(shù)字?jǐn)?shù)字P，使，使UPV）。你的任務(wù)是：對于從文件讀入的）。你的任務(wù)是：對于從文件讀入的一個一個Jam數(shù)字，按順序輸出緊接在后面的數(shù)字，按順序輸出緊接在后面的5個個Jam數(shù)字，如果后面沒有數(shù)字，如果后面沒有那么多那么多Jam數(shù)字，那么有幾個就輸出幾個。數(shù)字，那么有幾個就輸出幾個。 【輸入文件【輸入文件】輸入文件輸入文件counting.in 有有2行，第行，第1行為行為3個正整數(shù)，用一個空格隔開：個正整數(shù)，用一個空格隔開：s t w（其中（其中s為所使用的最小的字母的序號，為所使用的最

53、小的字母的序號，t為所使用的最大的字母的序號。為所使用的最大的字母的序號。w為數(shù)字的位數(shù)，這為數(shù)字的位數(shù)，這3個數(shù)滿足：個數(shù)滿足：1st26, 2wt-s ） 第第2行為具有行為具有w個小寫字母的字符串，為一個符合要求的個小寫字母的字符串，為一個符合要求的Jam數(shù)字。數(shù)字?！据敵鑫募据敵鑫募枯敵鑫募敵鑫募ounting.out 最多為最多為5行，為緊接在輸入的行，為緊接在輸入的Jam數(shù)字后面的數(shù)字后面的5個個Jam數(shù)字，如果后面沒有那么多數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個就輸出幾個。每行只數(shù)字，那么有幾個就輸出幾個。每行只輸出一個輸出一個Jam數(shù)字，是由數(shù)字，是由w個小寫字

54、母組成的字符串，不要有多余的空格。個小寫字母組成的字符串，不要有多余的空格?！据斎霕永据斎霕永?2 10 5 bdfij【輸出樣例【輸出樣例】bdghibdghjbdgijbdhijbefghvar i,j,s,t,w,n:longint; st:string; a:array0.30of integer;begin readln(s,t,w); readln(st);輸入起始字符串輸入起始字符串 for i:=1 to w do ai:=ord(sti)-(ord(a)+s)+2;將字符串轉(zhuǎn)變?yōu)閿?shù)字串將字符串轉(zhuǎn)變?yōu)閿?shù)字串 a0:=0;n:=0;控制開關(guān)變控制開關(guān)變0和生成個數(shù)清和生成個數(shù)

55、清0 while (a0=0)and(n0)do i:=i-1; inc(ai); for j:=i+1 to w do aj:=aj-1+1;產(chǎn)生下一個組合產(chǎn)生下一個組合 if a00 then begin halt; end else begin for i:=1 to w do write(chr(ord(a)+ai+s-2); writeln; n:=n+1;個數(shù)加個數(shù)加1 end; end;end.2 10 5bdfij先轉(zhuǎn)換：98-(97+2)+2=1 1 3 5 8 9初始組合i=5時，t-s-w+i+1=10-2-5+5+1=9 a5最大可取9產(chǎn)生下一個組合：1 3 6 7 8

56、輸出：i=1時,chr(97+1+2-2)=b bdghi排列組合題型總結(jié)排列組合題型總結(jié) 排列組合問題千變?nèi)f化，解法靈活，條件隱晦，思維排列組合問題千變?nèi)f化，解法靈活，條件隱晦，思維抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用題時，除做到：題時，除做到：排列組合分清，加乘原理辯明，避免重復(fù)排列組合分清，加乘原理辯明，避免重復(fù)遺漏遺漏外，還應(yīng)注意積累排列組合問題得以快速準(zhǔn)確求解。外，還應(yīng)注意積累排列組合問題得以快速準(zhǔn)確求解。直接法直接法1.特殊元素法特殊元素法 用用1 1，2 2，3 3，4 4，5 5，6 6這這6 6個數(shù)字組成無重復(fù)的

57、四位數(shù)，試個數(shù)字組成無重復(fù)的四位數(shù)，試求滿足下列條件的四位數(shù)各有多少個求滿足下列條件的四位數(shù)各有多少個（1 1）數(shù)字）數(shù)字1 1不排在個位和千位不排在個位和千位; ;（2 2）數(shù)字）數(shù)字1 1不在個位，數(shù)字不在個位，數(shù)字6 6不在千位。不在千位。分析：（分析：（1 1）個位和千位有）個位和千位有5 5個數(shù)字可供選擇個數(shù)字可供選擇 ，其余，其余2 2位有四個可供選擇位有四個可供選擇 ，由乘法原理：，由乘法原理： =240=240 25A24A25A24A特殊元素，優(yōu)先處理；特殊位置，優(yōu)先考慮 。2.2.特殊位置法特殊位置法 （2 2）當(dāng)）當(dāng)1 1在千位時余下三位有在千位時余下三位有 =60=60

58、，1 1不在千位時，千位不在千位時，千位有有 種選法，個位有種選法，個位有 種，余下的有種，余下的有 ，共有，共有 =192,=192,所以總共有所以總共有192+60=252192+60=25235A14A14A24A間接法間接法當(dāng)直接法求解類別比較大時，應(yīng)采用間接法。如上例中當(dāng)直接法求解類別比較大時，應(yīng)采用間接法。如上例中（2 2）可用間接法）可用間接法 有五張卡片，它的正反面分別寫有五張卡片，它的正反面分別寫0 0與與1 1，2 2與與3 3，4 4與與5 5，6 6與與7 7，8 8與與9 9，將它們?nèi)我馊龔埐⑴欧旁谝黄鸾M成三位數(shù)，將它們?nèi)我馊龔埐⑴欧旁谝黄鸾M成三位數(shù)，共可組成多少個不

59、同的三位數(shù)？共可組成多少個不同的三位數(shù)？ 分析：此例正面求解需考慮分析：此例正面求解需考慮0 0與與1 1卡片用與不用，且用此卡片卡片用與不用，且用此卡片 又分使用又分使用0 0與使用與使用1 1，類別較復(fù)雜，因而可使用間接計算：任，類別較復(fù)雜，因而可使用間接計算：任 取三張卡片可以組成不同的三位數(shù)取三張卡片可以組成不同的三位數(shù) 個，其中個，其中0 0在在 百位的有百位的有 個，這是不合題意的。故共可組成不個，這是不合題意的。故共可組成不 同的三位數(shù)同的三位數(shù) =432=432（個）（個）. .333352AC 8位同學(xué)排成一行，要求某兩位同學(xué)互不相位同學(xué)排成一行，要求某兩位同學(xué)互不相鄰，有多

60、少種排法？鄰，有多少種排法？8位同學(xué)排成一行的總數(shù)是位同學(xué)排成一行的總數(shù)是8！把排在一起的的兩個同學(xué)看成一個人的排列總數(shù)是把排在一起的的兩個同學(xué)看成一個人的排列總數(shù)是7！因為排在一起的兩個同學(xué)的位置可以互換，所以兩位因為排在一起的兩個同學(xué)的位置可以互換，所以兩位同學(xué)排在一起的排列數(shù)是同學(xué)排在一起的排列數(shù)是27！所以符合題意的個數(shù)為所以符合題意的個數(shù)為8！27！30240 正方體8個頂點(diǎn)中取出4個，可組成多少個四面體? 所求問題的方法數(shù)=任意選四點(diǎn)的組合數(shù)-共面四點(diǎn)的方法數(shù)， -12=70-12=58個。 48C插空法插空法 在一個含有在一個含有8個節(jié)目的節(jié)目單中，臨時插入兩個歌唱個節(jié)目的節(jié)目單