(最新整理)《排列組合專題》PPT課件

1、(最新整理)排列組合專題PPT課件2021/7/261加法原理和乘法原理 加法原理和乘法原理是排列組合的基礎(chǔ)和核心，既可用來(lái)推導(dǎo)排列數(shù)、組合數(shù)公式，也可用來(lái)直接解題。它們的共同點(diǎn)都是把一個(gè)事件分成若干個(gè)分事件來(lái)進(jìn)行計(jì)算。 利用加法原理，重在分“類”，類與類之間具有獨(dú)立性和并列性； 利用乘法原理，重在分步；步與步之間具有相依性和連續(xù)性。 比較復(fù)雜的問(wèn)題，常先分類再分步。2021/7/2621.加法原理: 如果完成一項(xiàng)工作有兩類相互獨(dú)立的方式A和B,在方式A中有m種完成任務(wù)的途徑,在方式B中有n種完成任務(wù)的途徑,則完成這項(xiàng)工作的總的途徑有m+n種.2.乘法原理: 如果完成一項(xiàng)工作有兩個(gè)連續(xù)的步驟A

2、和B,在步驟A中有m種不同的方式,在步驟B中有n種不同的方式,則完成這項(xiàng)工作的總的方法有m*n種.2021/7/263例1、 從1到4這4個(gè)數(shù)碼中不重復(fù)地任取3個(gè)構(gòu)成一個(gè)三位數(shù),求這樣的三位數(shù)一共有多少個(gè)?分析:構(gòu)成三位數(shù)的過(guò)程可以看成是由連續(xù)的三步完成:第一步:取百位上的數(shù)字,共有4種方法第二步:取十位上的數(shù)字,共有3種方法(即不能取百位上已經(jīng)取走的數(shù)碼)第三步:取個(gè)位上的數(shù)字,共有2種方法(即不能取百位和十位上已經(jīng)取走的數(shù)碼)因此由乘法原理,這樣的三位數(shù)一共有:4*3*2=24種.2021/7/264例2、 一個(gè)三位數(shù)，如果它的每一位數(shù)字都不小于另一個(gè)三位數(shù)對(duì)應(yīng)數(shù)位上的數(shù)字，就稱它“吃掉”

3、后一個(gè)三位數(shù)，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位數(shù)共有多少個(gè)？ 百位上有5、6、7、8、9五種選擇，十位上有8、9兩種選擇，個(gè)位上有7，8，9三種選擇，所以共有523=30（個(gè)）三位數(shù)。2021/7/265例3、 如圖，一方形花壇分成編號(hào)為，四塊，現(xiàn)有紅、黃、藍(lán)、紫四種顏色的花供選種，要求每塊只種一種顏色的花，且相鄰的兩塊種不同顏色的花。如果編號(hào)為的已經(jīng)種上紅色花，那么其余三塊不同的種法有 種。21 編號(hào)為的有三種選擇，對(duì)于編號(hào)為的，可以分成以下二類：1、若編號(hào)為的與編號(hào)為的同色，則編號(hào)為的有三種選擇。這種情況下共有33種方案。2、若編號(hào)為

4、的與編號(hào)為的不同色，則編號(hào)為的有二種選擇，編號(hào)為的有二種選擇。這種情況下共有322種方案。2021/7/266例4、 用紅、黃、綠、藍(lán)、黑五種顏色涂在如下圖所示的ABCDE五區(qū)域，顏色可重復(fù)使用，但同色不相鄰，涂法有幾種？ AC同色:5*4*4*1*4AC不同色:5*4*4*3*31040 2021/7/267例5、 在一塊并排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟，為有利于作物生長(zhǎng)，要求A，B兩種作物的間隔不少于6壟，不同的選法共有_種。分析：采取分類的方法。 第一類：A在第一壟，B有3種選擇；第二類：A在第二壟，B有2種選擇； 第三類：A在第三壟，B有一種選擇， 同理

5、A、B位置互換 ，共12種。 2021/7/268例6、 某小組有10人，每人至少會(huì)英語(yǔ)和日語(yǔ)的一門，其中8人會(huì)英語(yǔ)，5人會(huì)日語(yǔ)，從中選出會(huì)英語(yǔ)與會(huì)日語(yǔ)的各1人，有多少種不同的選法? 由于8+51310，所以10人中必有3人既會(huì)英語(yǔ)又會(huì)日語(yǔ)。（5+2+3）所以可分三類： 52 + 53 + 23=312021/7/269例7、 在所有的三位數(shù)中，有且只有兩個(gè)數(shù)字相同的三位數(shù)共有多少個(gè)? （1），（2），（3），（1），（2 ），（3）類中每類都是99種，共有99+99+99399243個(gè)只有兩個(gè)數(shù)字相同的三位數(shù)。 2021/7/2610例8、求正整數(shù)1400的正因數(shù)的個(gè)數(shù) 因?yàn)槿魏我粋€(gè)正整數(shù)的

6、任何一個(gè)正因數(shù)(除1外)都是這個(gè)數(shù)的一些質(zhì)因數(shù)的積，因此，我們先把1400分解成質(zhì)因數(shù)的連乘積1400=23527.所以這個(gè)數(shù)的任何一個(gè)正因數(shù)都是由2，5，7中的若干個(gè)相乘而得到(有的可重復(fù))。 于是取1400的一個(gè)正因數(shù)，這件事情是分如下三個(gè)步驟完成的：(1)取23的正因數(shù)是20，21，22，23，共3+1種；(2)取52的正因數(shù)是50，51，52，共2+1種；(3)取7的正因數(shù)是70，71，共1+1種所以1400的正因數(shù)個(gè)數(shù)為(3+1)(2+1)(1+1)=242021/7/2611例9、 從1到300的自然數(shù)中，完全不含有數(shù)字3的有多少個(gè)？ 將0到299的整數(shù)都看成三位數(shù)，其中數(shù)字3不出

7、現(xiàn)的，百位數(shù)字可以是0，1或2三種情況。十位數(shù)字與個(gè)位數(shù)字均有九種，因此除去0共有3991=242(個(gè))2021/7/2612例10、 在小于10000的自然數(shù)中，含有數(shù)字1的數(shù)有多少個(gè)？ 不妨將0至9999的自然數(shù)均看作四位數(shù)，凡位數(shù)不到四位的自然數(shù)在前面補(bǔ)0,使之成為四位數(shù)。先求不含數(shù)字1的這樣的四位數(shù)共有幾個(gè)，即有0，2，3，4，5，6，7，8，9這九個(gè)數(shù)字所組成的四位數(shù)的個(gè)數(shù)。由于每一位都可有9種寫法，所以，根據(jù)乘法原理，由這九個(gè)數(shù)字組成的四位數(shù)個(gè)數(shù)為99996561。 于是，小于10000且含有數(shù)字1的自然數(shù)共有9999-6561=3438個(gè)2021/7/2613排列的定義 數(shù)學(xué)上，

8、把若干元素，按照任何一種順序排成一列，叫做排列。 如果兩個(gè)排列滿足下列條件之一，它們就被認(rèn)為是不同的排列： 1.所含元素不全相同 2.所含元素相同，但順序不同。2021/7/2614相異元素不重復(fù)的排列 從 n個(gè)不同的元素中，取出r個(gè)不重復(fù)的元素，按次序排成一列，當(dāng)rn時(shí)，稱為從n個(gè)中取r個(gè)的一種選排列。如：從a,b,c這三個(gè)字母中，每次取出2個(gè)，有多少種排列方法?第一步：確定左邊的字母，在三個(gè)字母中任取一個(gè)，有種方法；第二步：確定右邊的字母，從剩下的個(gè)字母中選取一個(gè)，有種方法；根據(jù)乘法原理，共有種不同的排法. ab ac ba bc ca cb 2021/7/2615 一般地，從n個(gè)不同的元

9、素中取出r個(gè)元素的選排列數(shù)用 表示，則 n!/(n-r)!2021/7/2616例全國(guó)足球甲級(jí)（組）聯(lián)賽共有隊(duì)參加，每隊(duì)都要與其它各隊(duì)在主、客場(chǎng)分別比賽一次，共進(jìn)行多少場(chǎng)比賽？ 任何二個(gè)隊(duì)進(jìn)行一次主場(chǎng)比賽和一場(chǎng)客場(chǎng)比賽，相當(dāng)于從14個(gè)元素中任取2個(gè)元素的一個(gè)排列，共需進(jìn)行的比賽場(chǎng)次是 =14!/12!=14*13=1822021/7/2617當(dāng)n=r時(shí),叫做n個(gè)不同元素的全排列n個(gè)不同元素的全排列數(shù)Pnn n!例個(gè)人站成一排照相，共有多少種不同的排列方法？ !2021/7/2618例3、求有多少個(gè)沒有重復(fù)數(shù)字且能被5整除的四位奇數(shù)。 要能被5整除又是奇數(shù)，所以個(gè)位上數(shù)字只能是5,有1種選法，由

10、于5已用過(guò)，又不可能是0,所以千位上數(shù)有P18種選法,已用過(guò)2個(gè)數(shù)，所以百位、十位上的數(shù)有P28種選法。 所以符合題意的個(gè)數(shù)為： 1 P18 P284482021/7/2619例4、用0、1、2、3、4、5六個(gè)數(shù)字，可以組成多少個(gè)沒有重復(fù)數(shù)字的三位偶數(shù)？1.個(gè)位為0,十位為1、2、3、4、5中的一個(gè)，百位為剩下的四個(gè)數(shù)字中的一個(gè)，所以這樣的偶數(shù)共有1P15P142.個(gè)位為2,百位為1、3、4、5中的一個(gè)，十位為剩下的四個(gè)數(shù)字中的一個(gè)，所以這樣的偶數(shù)共有1P14P143.個(gè)位為4,百位為1、2、3、5中的一個(gè)，十位為剩下的四個(gè)數(shù)字中的一個(gè)，所以這樣的偶數(shù)共有1P14P14所以符合題意的個(gè)數(shù)為20

11、1616522021/7/2620例5、 8位同學(xué)排成相等的兩行，要求某兩位同學(xué)必須排在前排，有多少種排法？ 這兩個(gè)同學(xué)排在前排4個(gè)位置的排列數(shù)是P24，其它同學(xué)在余下的6個(gè)位置排的排列數(shù)是6！，所以符合題意的個(gè)數(shù)為P246！127208640。2021/7/2621例6、某車站有編號(hào)為1到6的6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，問(wèn)一個(gè)小組4人進(jìn)站的方案有幾種？第一個(gè)人有6種方案，第二個(gè)人有7種方案，因?yàn)樗x擇和第一個(gè)人相同入口處時(shí)，還有前后之分9*8*7*6=3024 o o oo 在兩個(gè)入口之間加一個(gè)標(biāo)志，共5個(gè)無(wú)區(qū)別的標(biāo)志，問(wèn)題歸結(jié)為9個(gè)元素中有5個(gè)無(wú)區(qū)別的元素，4個(gè)不同元素的排列數(shù)。

12、所以4個(gè)人進(jìn)站的方案數(shù)有：9！/5！9*8*7*6=30242021/7/2622相異元素的可重復(fù)排列 從n個(gè)不同元素中取出r個(gè)元素的可重復(fù)的排列種數(shù)為nr.93=729例7由數(shù)字1,2,3,9共能組成多少個(gè)三位數(shù)？2021/7/2623相異元素的循環(huán)排列 n個(gè)不同元素不分首尾排成一個(gè)圓圈，稱為循環(huán)排列。其排列數(shù)為n!/n=(n-1)!。 如1,2,3三個(gè)數(shù)的循環(huán)排列只有，二種。2021/7/2624例8在圓形花壇外側(cè)擺放盆菊花和盆蘭花，要求蘭花不能相鄰擺放，一共有多少種擺法？盆菊花擺成一周的排列方法有n1=！盆蘭花插入個(gè)空中的排列總數(shù)有n2=P=8!/4!擺放總數(shù)為n=n1*n2=84672

13、002021/7/2625例9有男女各五個(gè)人，其中有對(duì)是夫妻，沿圓桌就座，若每對(duì)夫妻都坐在相鄰的位置，問(wèn)有多少種坐法？設(shè)對(duì)夫妻分別為和a,和b,和c，先讓，三人和另外個(gè)人沿圓桌就座的方法為！種又對(duì)上述每種坐法，a坐在的鄰座的方式有左右兩種，b,c也如此所以共有！種2021/7/2626不全相異元素的排列 如果在n個(gè)元素中，有n1個(gè)元素彼此相同，有n2個(gè)元素彼此相同，,又有nm個(gè)元素彼此相同，若n1+n2+nm=n，則這n個(gè)元素的全排列叫做不全相異元素的全排列，其排列數(shù)為: n!/(n1!*n2!*nm!). 若n1+n2+nm=rn，則這n個(gè)元素的全排列叫做不全相異元素的選排列，其排列數(shù)為:

14、prn/(n1!*n2!*nm!).2021/7/2627例10、將N個(gè)紅球和M個(gè)黃球排成一行。如:N=2,M=3可得到10種排法。問(wèn)題:當(dāng)N=4,M=3時(shí)有 種不同排法?7!/(4!*3!)=35NOIP2002 2021/7/2628例11、把兩個(gè)紅球、一個(gè)藍(lán)球和一個(gè)白球放到十個(gè)編號(hào)不同的盒子中去，有多少種方法？排列數(shù)為p410/(2!*1!*1!)25202021/7/2629生成排列的算法 下面程序的功能是利用遞歸方法生成從1到n(n10)的n個(gè)數(shù)的全部可能的排列（不一定按升序輸出）。 例如，輸入3，則應(yīng)該輸出（每行輸出5個(gè)排列）： 123 132 213 231 321 312 求全

15、排列(06年初賽題)2021/7/2630var i,n,k:integer; a:array1.10 of integer; count:longint; procedure perm( k:integer); var j,p,t:integer; begin if( )then begin ( ); for p:=1 to k do write(ap:1); write( ); if( )then writeln; exit; end; for j:=k to n do begin t:=ak; ak:=aj; aj:=t; perm(k+1) ; t:=ak;( ) end end; b

16、egin writeln(Entry n:); read(n); count:=0; for i:=1 to n do ai:=i; ( ) end.perm(1)K=ninc(count)count mod 5=0ak:=aj; aj:=t ;123 132 213 231 321 3122021/7/2631算法過(guò)程:用數(shù)組：a:array1.r of integer ;表示排列; 初始化時(shí)，ai:=i(i=1,2,r);設(shè)中間的某一個(gè)排列為a1,a2,，ar，則求出下一個(gè)排列的算法為：從后面向前找，直到找到一個(gè)順序?yàn)橹梗ㄔO(shè)下標(biāo)為j-1,則aj-1aj）從aj ar中，找出一個(gè)比aj-1大

17、的最小元素ak將aj-1與ak交換將aj，aj+1ar由小到大排序。 問(wèn)題描述: 用生成法求出1，2，r的全排列(raj(ai1aj-1)and(ai1ak1 3 2 5 41 3 4 5 21 3 4 2 52021/7/2633【問(wèn)題描述】 人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無(wú)法理解對(duì)方的語(yǔ)言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個(gè)非常大的數(shù)字告訴人類科學(xué)家，科學(xué)家破解這個(gè)數(shù)字的含義后，再把一個(gè)很小的數(shù)字加到這個(gè)大數(shù)上面，把結(jié)果告訴火星人，作為人類的回答。 火星人用一種非常簡(jiǎn)單的方式來(lái)表示數(shù)字掰手指?；鹦侨酥挥幸恢皇?/p>

18、，但這只手上有成千上萬(wàn)的手指，這些手指排成一列，分別編號(hào)為1，2，3?；鹦侨说娜我鈨筛种付寄茈S意交換位置，他們就是通過(guò)這方法計(jì)數(shù)的。一個(gè)火星人用一個(gè)人類的手演示了如何用手指計(jì)數(shù)。如果把五根手指拇指、食指、中指、無(wú)名指和小指分別編號(hào)為1，2，3，4和5，當(dāng)它們按正常順序排列時(shí)，形成了5位數(shù)12345，當(dāng)你交換無(wú)名指和小指的位置時(shí)，會(huì)形成5位數(shù)12354，當(dāng)你把五個(gè)手指的順序完全顛倒時(shí)，會(huì)形成54321，在所有能夠形成的120個(gè)5位數(shù)中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指時(shí)能夠形成的6個(gè)3位數(shù)和它們代表的數(shù)字：三進(jìn)制數(shù)123

19、132213231312321代表的數(shù)字123456火星人（04年普及組）2021/7/2634 現(xiàn)在你有幸成為了第一個(gè)和火星人交流的地球人。一個(gè)火星人會(huì)讓你看他的手指，科學(xué)家會(huì)告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個(gè)結(jié)果不會(huì)超出火星人手指能表示的范圍。【輸入文件】輸入文件martian.in包括三行，第一行有一個(gè)正整數(shù)N，表示火星人手指的數(shù)目（1 = N = 10000）。第二行是一個(gè)正整數(shù)M，表示要加上去的小整數(shù)（1 = M = 100）。下一行是1到N這N個(gè)整數(shù)的一個(gè)排列，用空格隔開，表

20、示火星人手指的排列順序?！据敵鑫募枯敵鑫募artian.out只有一行，這一行含有N個(gè)整數(shù)，表示改變后的火星人手指的排列順序。每?jī)蓚€(gè)相鄰的數(shù)中間用一個(gè)空格分開，不能有多余的空格?！緲永斎搿?31 2 3 4 5【樣例輸出】1 2 4 5 3【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，N=15；對(duì)于60%的數(shù)據(jù)，N=50；對(duì)于全部的數(shù)據(jù)，N0 do一次循環(huán)產(chǎn)生下一個(gè)排列 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 tem

21、p:=ai; ai:=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 2021/7/2637組合的定義 數(shù)學(xué)上，把若干元素，不論次序并成一組，叫做組合。 如果兩個(gè)組合中，至少有一個(gè)元素不同，它們就被認(rèn)為是不同的組合。abc,abd2021/7/2638相異元素不重復(fù)的組合 設(shè)從n個(gè)不同的元素中，取出m個(gè)不同元素，不考慮順序并成一組，叫作從n個(gè)不同的元素中，取出m個(gè)不同元素的一

22、個(gè)組合。如：寫出從a,b,c,d四個(gè)元素中，任取三個(gè)元素的所有組合。abc, abd, acd, bcd從n個(gè)不同的元素中，取出m個(gè)不同元素的組合數(shù)記為Cmn;則有CmnPmn/m!=n!/m!(n-m)!規(guī)定C0n=1abc,bac,cab,acb,bca,cba2021/7/2639例1、八年級(jí)6個(gè)班進(jìn)行排球比賽，每班的排球隊(duì)要與其他5個(gè)班分別比賽一場(chǎng)，求共要進(jìn)行多少場(chǎng)比賽？C26P26/2!=6*5/2*1=152021/7/2640例2、平面上有n個(gè)點(diǎn)且無(wú)三點(diǎn)或三點(diǎn)以上共線，任意兩點(diǎn)可以連成一條直線，一共能連成多少條直線？ C2nn*(n-1)/22021/7/2641例3、某班第一組

23、有10名同學(xué)，第二組有8名同學(xué)，現(xiàn)要求每組選出2名學(xué)生代表參加座談會(huì)，有多少種選法？C210C2812602021/7/2642例4.一元、二元、五元、十元人民幣各一張，一共可以組成多少種不同的幣值？ C14C24C34C444641152021/7/2643例5、5年級(jí)有8個(gè)班，六年級(jí)有6個(gè)班，先分別舉行各年級(jí)的籃球賽，采用單循環(huán)制，然后由兩個(gè)年級(jí)的第一名爭(zhēng)奪冠軍，共需要比賽多少場(chǎng)？ C28C26+1=8*7/2+6*5/2+1=28+15+1=442021/7/2644例6：某班第一組有10名同學(xué)，其中有4名女同學(xué)，現(xiàn)要求選出3名學(xué)生代表,其中至少有一名女同學(xué)去參加座談會(huì)，有多少種選法？

24、代表中有1名女同學(xué)的選法為C14C26種， 代表中有2名女同學(xué)的選法為C24C16種， 代表中有3名女同學(xué)的選法為C34種，C14C26C24C16C341002021/7/2645例7、欲登上第10級(jí)樓梯，如果規(guī)定每步只能跨上一級(jí)或兩級(jí)，則不同的走法共有( )。 2021/7/2646例8、A的一邊AB上有4個(gè)點(diǎn)，另一邊AC上有5個(gè)點(diǎn)，連同A的頂點(diǎn)共10個(gè)點(diǎn)，以這些點(diǎn)為頂點(diǎn)，可以構(gòu)成_個(gè)三角形. 902021/7/2647例9、平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？（2001年p）C(7,2)*(

25、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+210=7512021/7/2648例10、平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形?（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=22502021/7/2649

26、 例11、10名劃船運(yùn)動(dòng)員中，3人只會(huì)劃左舷，2人只會(huì)劃右舷，5人左右舷都會(huì)劃，從中選6人，平均分在左、右舷，共有多少種不同的選法？ 1.會(huì)劃左舷的全劃左舷：2.派一個(gè)全能劃左舷：3.派二個(gè)全能劃左舷：4.派三個(gè)全能劃左舷：6752021/7/2650例12、小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如a2-b2-a3-b3是合法的，而a2-b3-a

27、3-b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有 種。(2009年p) 70 2021/7/2651排列組合+加法原理:B任務(wù)中的b1一定做，而且肯定是第一個(gè)做的。除了b1外，第一類：完成A任務(wù) 只有1種。第二類：完成A任務(wù)和b2 有C(4,1)=4種。第三類：完成A任務(wù)和b2、b3 有C(5,2)=10種。第四類：完成A任務(wù)和b2、b3、b4 有C(6,3)=20種。第五類：完成A任務(wù)和b2、b3、b4、b5 有C(7,4)=35種。加起來(lái)1+

28、4+10+20+35=70。b2 a1 a2 a3a1 b2 a2 a3a1 a2 b2 a3a1 a2 a3 b2 2021/7/2652例13、袋中有已編號(hào)的20個(gè)球，其中110號(hào)是紅球，1120號(hào)是白球，每取得一個(gè)紅球得2分，取得一個(gè)白球得3分，若取得若干個(gè)球，共得20分，有多少種不同取法？2x+3y=20, y必是偶數(shù)，所以y=0,2,4,6；相應(yīng)地x=10,7,4,1； C010C1010C210C710 C410C410 C610C110 516012021/7/2653例14、從1300之間任取3個(gè)不同的數(shù)，使得這3個(gè)數(shù)的和恰好被3除盡，有多少種方法？ 被3除所得的余數(shù)不外乎：0

29、，1，2。所以可把1300之間的數(shù)分成三組： A1,4,7,298 B2,5,8,299 C3,6,9,300 三個(gè)數(shù)同屬于集合A，有C3100種， 三個(gè)數(shù)同屬于集合B，有C3100種， 三個(gè)數(shù)同屬于集合C，有C3100種， 三個(gè)數(shù)分屬于集合A，B，C，有1003種。加起來(lái)等于 1485100種。2021/7/2654例15、若將一個(gè)正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字0的個(gè)數(shù)多于數(shù)字1的個(gè)數(shù)的這類二進(jìn)制數(shù)稱為A類數(shù)。 例如： （24）10=（11000）2 其中1的個(gè)數(shù)為2，0的個(gè)數(shù)為3，則稱此數(shù)為A類數(shù)； 請(qǐng)你求出1112之中（包括1與112），全部A類數(shù)的個(gè)數(shù)。 （112）10

30、=（1110000）2可根據(jù)二進(jìn)制數(shù)的前綴來(lái)分類。2021/7/2655111：這類數(shù)中A類數(shù)只有一個(gè)，即1110000110：這類數(shù)中A類數(shù)個(gè)數(shù)為： C44C34510：這類數(shù)中A類數(shù)個(gè)數(shù)為： C55C45 C35 160：位數(shù)不確定，需對(duì)位數(shù)進(jìn)行討論。2021/7/26561位數(shù)，即1,不是A類數(shù)，2位數(shù)，即1，10和11都不是A類數(shù)，3位數(shù)，即1，只有100一個(gè)，4位數(shù)，即1，只有1000一個(gè)，5位數(shù)，即1， A類數(shù)個(gè)數(shù)有C44C345,6位數(shù)，即1， A類數(shù)個(gè)數(shù)有C55C456,1516（1156）352021/7/2657例16、 某城市有4條東西街道和6條南北的街道，街道之間的間距

31、相同。若規(guī)定只能向東或向北兩個(gè)方向沿圖中路線前進(jìn)，則從M到N有多少種不同的走法?(2007年p) MN（一）從M到N必須向上走三步，向右走五步，共走八步。 （二）每一步是向上還是向右，決定了不同的走法。 （三）事實(shí)上，當(dāng)把向上的步驟決定后，剩下的步驟只能向右。 從而，任務(wù)可敘述為：從八個(gè)步驟中選出哪三步是向上走，就可以確定走法數(shù)。 本題答案為56。 2021/7/2658相異元素的可重復(fù)組合 設(shè)從n個(gè)不同的元素中，取出m個(gè)不同元素，若允許這個(gè)元素可以重復(fù)使用，也允許mn，則把這樣的組合稱為重復(fù)組合，其組合數(shù)記為Hmn。 Hmn=Cmn+m-1 如1,2,3,4,四個(gè)數(shù)字中取三個(gè)，允許重復(fù)的組合

32、有以下20種： 111, 122, 134, 224, 333 112, 123, 144, 233, 334 113, 124, 222, 234, 344 114, 133, 223, 244, 4442021/7/2659組合的生成算法 從1,2,3,n共n個(gè)數(shù)中任取m個(gè)數(shù)，請(qǐng)輸出所有組合并計(jì)算組合數(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:

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

34、，英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為Jam數(shù)字。在Jam數(shù)字中，每個(gè)字母互不相同，而且從左到右是嚴(yán)格遞增的。每次，Jam還指定使用字母的范圍，例如，從2到10，表示只能使用b,c,d,e,f,g,h,i,j這些字母。如果再規(guī)定位數(shù)為5，那么，緊接在Jam數(shù)字“bdfij”之后的數(shù)字應(yīng)該是“bdghi”。（如果我們用U、V依次表示Jam數(shù)字“bdfij”與“bdghi”，則UV，且不存在Jam數(shù)字P，使UPV）。你的任務(wù)是：對(duì)于從文件讀入的一個(gè)Jam數(shù)字，按順序輸出緊接在后面的5個(gè)Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個(gè)就輸出幾個(gè)。20

35、21/7/2661 【輸入文件】輸入文件counting.in 有2行，第1行為3個(gè)正整數(shù)，用一個(gè)空格隔開：s t w（其中s為所使用的最小的字母的序號(hào)，t為所使用的最大的字母的序號(hào)。w為數(shù)字的位數(shù)，這3個(gè)數(shù)滿足：1st26, 2wt-s ） 第2行為具有w個(gè)小寫字母的字符串，為一個(gè)符合要求的Jam數(shù)字?！据敵鑫募枯敵鑫募ounting.out 最多為5行，為緊接在輸入的Jam數(shù)字后面的5個(gè)Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個(gè)就輸出幾個(gè)。每行只輸出一個(gè)Jam數(shù)字，是由w個(gè)小寫字母組成的字符串，不要有多余的空格?！据斎霕永?2 10 5 bdfij【輸出樣例】bdghibd

36、ghjbdgijbdhijbefgh2021/7/2662var 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ù)字串 a0:=0;n:=0;控制開關(guān)變0和生成個(gè)數(shù)清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)生下一個(gè)組合 if a00 then begin

37、 halt; end else begin for i:=1 to w do write(chr(ord(a)+ai+s-2); writeln; n:=n+1;個(gè)數(shù)加1 end; end;end.2 10 5bdfij先轉(zhuǎn)換：98-(97+2)+2=1 1 3 5 8 9初始組合i=5時(shí)，t-s-w+i+1=10-2-5+5+1=9 a5最大可取9產(chǎn)生下一個(gè)組合：1 3 6 7 8輸出：i=1時(shí),chr(97+1+2-2)=b bdghi2021/7/2663排列組合題型總結(jié) 排列組合問(wèn)題千變?nèi)f化，解法靈活，條件隱晦，思維抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用題時(shí)，除做到：排列組

38、合分清，加乘原理辯明，避免重復(fù)遺漏外，還應(yīng)注意積累排列組合問(wèn)題得以快速準(zhǔn)確求解。2021/7/2664直接法1.特殊元素法 用1，2，3，4，5，6這6個(gè)數(shù)字組成無(wú)重復(fù)的四位數(shù)，試求滿足下列條件的四位數(shù)各有多少個(gè)（1）數(shù)字1不排在個(gè)位和千位;（2）數(shù)字1不在個(gè)位，數(shù)字6不在千位。分析：（1）個(gè)位和千位有5個(gè)數(shù)字可供選擇 ，其余2位有四個(gè)可供選擇 ，由乘法原理： =240 特殊元素，優(yōu)先處理；特殊位置，優(yōu)先考慮 。2021/7/26652.特殊位置法 （2）當(dāng)1在千位時(shí)余下三位有 =60，1不在千位時(shí)，千位有 種選法，個(gè)位有 種，余下的有 ，共有 =192,所以總共有192+60=2522021

39、/7/2666間接法當(dāng)直接法求解類別比較大時(shí)，應(yīng)采用間接法。如上例中（2）可用間接法 2021/7/2667 有五張卡片，它的正反面分別寫0與1，2與3，4與5，6與7，8與9，將它們?nèi)我馊龔埐⑴欧旁谝黄鸾M成三位數(shù)，共可組成多少個(gè)不同的三位數(shù)？ 分析：此例正面求解需考慮0與1卡片用與不用，且用此卡片 又分使用0與使用1，類別較復(fù)雜，因而可使用間接計(jì)算：任 取三張卡片可以組成不同的三位數(shù) 個(gè)，其中0在 百位的有 個(gè)，這是不合題意的。故共可組成不 同的三位數(shù) =432（個(gè)）.2021/7/2668 8位同學(xué)排成一行，要求某兩位同學(xué)互不相鄰，有多少種排法？8位同學(xué)排成一行的總數(shù)是8！把排在一起的的兩

40、個(gè)同學(xué)看成一個(gè)人的排列總數(shù)是7！因?yàn)榕旁谝黄鸬膬蓚€(gè)同學(xué)的位置可以互換，所以兩位同學(xué)排在一起的排列數(shù)是27！所以符合題意的個(gè)數(shù)為8！27！302402021/7/2669 正方體8個(gè)頂點(diǎn)中取出4個(gè)，可組成多少個(gè)四面體? 所求問(wèn)題的方法數(shù)=任意選四點(diǎn)的組合數(shù)-共面四點(diǎn)的方法數(shù)， -12=70-12=58個(gè)。 2021/7/2670插空法 在一個(gè)含有8個(gè)節(jié)目的節(jié)目單中，臨時(shí)插入兩個(gè)歌唱節(jié)目，且保持原節(jié)目順序，有多少種插入方法？ 原有的8個(gè)節(jié)目中含有9個(gè)空檔，插入一個(gè)節(jié)目后，空檔變?yōu)?0個(gè)，故有 =90中插入方法。 2021/7/2671 8位同學(xué)排成一行，其中有4位女同學(xué)，要求女同學(xué)不相鄰，有多少種

41、排法？ 四位男同學(xué)排成一行的總數(shù)是4！，在他們首尾兩個(gè)位置和他們兩兩之間的位置（共5個(gè)）分別插入一個(gè)女同學(xué)的排列數(shù)是A45120，所以符合題意的個(gè)數(shù)是4！12028802021/7/2672 馬路上有編號(hào)為l，2，3，10 十個(gè)路燈，為節(jié)約用電又看清路面，可以把其中的三只燈關(guān)掉，但不能同時(shí)關(guān)掉相鄰的兩只或三只，在兩端的燈也不能關(guān)掉的情況下，求滿足條件的關(guān)燈方法共有多少種? 關(guān)掉的燈不能相鄰，也不能在兩端。又因?yàn)闊襞c燈之間沒有區(qū)別，因而問(wèn)題為在7盞亮著的燈形成的不包含兩端的6個(gè)空中選出3個(gè)空放置熄滅的燈。 共 =20種方法。 2021/7/2673捆綁法當(dāng)需排元素中有必須相鄰的元素時(shí)，宜用捆綁法

42、。 4名男生和3名女生共坐一排，男生必須排在一起的坐法有多少種？分析：先將男生捆綁在一起看成一個(gè)大元素與女生全排列有 種排法，而男生之間又有 種排法，由乘法原理滿足條件的排法有： =5762021/7/2674 四個(gè)不同的小球全部放入三個(gè)不同的盒子中，若使每個(gè)盒子不空，則不同的放法有 種 。一定有兩個(gè)球放在同一個(gè)盒子中2021/7/2675 某市植物園要在30天內(nèi)接待20所學(xué)校的學(xué)生參觀，但每天只能安排一所學(xué)校，其中有一所學(xué)校人數(shù)較多，要安排連續(xù)參觀2天，其余只參觀一天，則植物園30天內(nèi)不同的安排方法有（ ）. 注意連續(xù)參觀2天，即需把30天中的連續(xù)兩天捆綁看成一天作為一個(gè)整體來(lái)選有 ，其余的

43、就是19所學(xué)校選28天進(jìn)行排列。2021/7/2676 書架上有四本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這四本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有（ ）種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有（ ）種擺法。（2008年p）2021/7/2677閘板法名額分配或相同物品的分配問(wèn)題，適宜采用閘板法. 某校準(zhǔn)備組建一個(gè)由12人組成的籃球隊(duì)，這12個(gè)人由8個(gè)班的學(xué)生組成，每班至少一人，名額分配方案共 種 。分析：此例的實(shí)質(zhì)是12個(gè)名額分配給8個(gè)班，每班至少一個(gè)名額，可在12個(gè)名額中的11個(gè)空當(dāng)中插入7塊閘板，一種插法對(duì)應(yīng)一種名額的分配方式，故有 種。2021/7/2678 若m,nN,mn，把n寫成m個(gè)自然數(shù)之和，如：m3,n5時(shí)，5113131311221212122. 問(wèn)共有多少種表示法？511（111）1（111）1（111）11（11）（11）1（11）1（11）1（11）（11）對(duì)n=1+1+1+1有幾種加括