排列組合專題第1頁，共85頁，2023年，2月20日，星期五1.加法原理:

如果完成一項工作有兩類相互獨立的方式A和B,在方式A中有m種完成任務(wù)的途徑,在方式B中有n種完成任務(wù)的途徑,則完成這項工作的總的途徑有m+n種.2.乘法原理:

如果完成一項工作有兩個連續(xù)的步驟A和B,在步驟A中有m種不同的方式,在步驟B中有n種不同的方式,則完成這項工作的總的方法有m*n種.第2頁，共85頁，2023年，2月20日，星期五例1、從1到4這4個數(shù)碼中不重復(fù)地任取3個構(gòu)成一個三位數(shù),求這樣的三位數(shù)一共有多少個?分析:構(gòu)成三位數(shù)的過程可以看成是由連續(xù)的三步完成:第一步:取百位上的數(shù)字,共有4種方法第二步:取十位上的數(shù)字,共有3種方法(即不能取百位上已經(jīng)取走的數(shù)碼)第三步:取個位上的數(shù)字,共有2種方法(即不能取百位和十位上已經(jīng)取走的數(shù)碼)因此由乘法原理,這樣的三位數(shù)一共有:4*3*2=24種.第3頁，共85頁，2023年，2月20日，星期五例2、一個三位數(shù)，如果它的每一位數(shù)字都不小于另一個三位數(shù)對應(yīng)數(shù)位上的數(shù)字，就稱它“吃掉”后一個三位數(shù)，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位數(shù)共有多少個？百位上有5、6、7、8、9五種選擇，十位上有8、9兩種選擇，個位上有7，8，9三種選擇，所以共有5×2×3=30（個）三位數(shù)。第4頁，共85頁，2023年，2月20日，星期五例3、如圖，一方形花壇分成編號為①，②，③，④四塊，現(xiàn)有紅、黃、藍、紫四種顏色的花供選種，要求每塊只種一種顏色的花，且相鄰的兩塊種不同顏色的花。如果編號為①的已經(jīng)種上紅色花，那么其余三塊不同的種法有

種。21

編號為②的有三種選擇，對于編號為③的，可以分成以下二類：1、若編號為④的與編號為②的同色，則編號為③的有三種選擇。這種情況下共有3×3種方案。2、若編號為④的與編號為②的不同色，則編號為③的有二種選擇，編號為④的有二種選擇。這種情況下共有3×2×2種方案。第5頁，共85頁，2023年，2月20日，星期五例4、用紅、黃、綠、藍、黑五種顏色涂在如下圖所示的ABCDE五區(qū)域，顏色可重復(fù)使用，但同色不相鄰，涂法有幾種？

AC同色:5*4*4*1*4AC不同色:5*4*4*3*31040

第6頁，共85頁，2023年，2月20日，星期五例5、在一塊并排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟，為有利于作物生長，要求A，B兩種作物的間隔不少于6壟，不同的選法共有______種。分析：采取分類的方法。第一類：A在第一壟，B有3種選擇；第二類：A在第二壟，B有2種選擇；第三類：A在第三壟，B有一種選擇，同理A、B位置互換，共12種。第7頁，共85頁，2023年，2月20日，星期五例6、某小組有10人，每人至少會英語和日語的一門，其中8人會英語，5人會日語，從中選出會英語與會日語的各1人，有多少種不同的選法?

由于8+5＝13＞10，所以10人中必有3人既會英語又會日語。（5+2+3）所以可分三類：

5×2+5×3+2×3=31第8頁，共85頁，2023年，2月20日，星期五例7、在所有的三位數(shù)中，有且只有兩個數(shù)字相同的三位數(shù)共有多少個?

（1）△△□，（2）△□△，（3）□△□，（1），（2

），（3）類中每類都是9×9種，共有9×9+9×9+9×9＝3×9×9＝243個只有兩個數(shù)字相同的三位數(shù)。

第9頁，共85頁，2023年，2月20日，星期五例8、求正整數(shù)1400的正因數(shù)的個數(shù)．因為任何一個正整數(shù)的任何一個正因數(shù)(除1外)都是這個數(shù)的一些質(zhì)因數(shù)的積，因此，我們先把1400分解成質(zhì)因數(shù)的連乘積1400=23527.所以這個數(shù)的任何一個正因數(shù)都是由2，5，7中的若干個相乘而得到(有的可重復(fù))。于是取1400的一個正因數(shù)，這件事情是分如下三個步驟完成的：

(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ù)個數(shù)為(3+1)×(2+1)×(1+1)=24．第10頁，共85頁，2023年，2月20日，星期五例9、從1到300的自然數(shù)中，完全不含有數(shù)字3的有多少個？將0到299的整數(shù)都看成三位數(shù)，其中數(shù)字3不出現(xiàn)的，百位數(shù)字可以是0，1或2三種情況。十位數(shù)字與個位數(shù)字均有九種，因此除去0共有3×9×9－1=242(個)．第11頁，共85頁，2023年，2月20日，星期五例10、在小于10000的自然數(shù)中，含有數(shù)字1的數(shù)有多少個？不妨將0至9999的自然數(shù)均看作四位數(shù)，凡位數(shù)不到四位的自然數(shù)在前面補0,使之成為四位數(shù)。

先求不含數(shù)字1的這樣的四位數(shù)共有幾個，即有0，2，3，4，5，6，7，8，9這九個數(shù)字所組成的四位數(shù)的個數(shù)。由于每一位都可有9種寫法，所以，根據(jù)乘法原理，由這九個數(shù)字組成的四位數(shù)個數(shù)為9×9×9×9＝6561。

于是，小于10000且含有數(shù)字1的自然數(shù)共有9999-6561=3438個．第12頁，共85頁，2023年，2月20日，星期五排列的定義數(shù)學(xué)上，把若干元素，按照任何一種順序排成一列，叫做排列。如果兩個排列滿足下列條件之一，它們就被認為是不同的排列：

1.所含元素不全相同

2.所含元素相同，但順序不同。第13頁，共85頁，2023年，2月20日，星期五相異元素不重復(fù)的排列從n個不同的元素中，取出r個不重復(fù)的元素，按次序排成一列，當r<n時，稱為從n個中取r個的一種選排列。如：從a,b,c這三個字母中，每次取出2個，有多少種排列方法?第一步：確定左邊的字母，在三個字母中任取一個，有３種方法；第二步：確定右邊的字母，從剩下的２個字母中選取一個，有２種方法；根據(jù)乘法原理，共有３×２＝６種不同的排法.abacbabccacb

第14頁，共85頁，2023年，2月20日，星期五一般地，從n個不同的元素中取出r個元素的選排列數(shù)用表示，則＝n!/(n-r)!第15頁，共85頁，2023年，2月20日，星期五例１．全國足球甲級（Ａ組）聯(lián)賽共有１４隊參加，每隊都要與其它各隊在主、客場分別比賽一次，共進行多少場比賽？任何二個隊進行一次主場比賽和一場客場比賽，相當于從14個元素中任取2個元素的一個排列，共需進行的比賽場次是

=14!/12!=14*13=182第16頁，共85頁，2023年，2月20日，星期五當n=r時,叫做n個不同元素的全排列．n個不同元素的全排列數(shù)Pnn

＝n!例２．３個人站成一排照相，共有多少種不同的排列方法？＝３!＝６第17頁，共85頁，2023年，2月20日，星期五例3、求有多少個沒有重復(fù)數(shù)字且能被5整除的四位奇數(shù)。要能被5整除又是奇數(shù)，所以個位上數(shù)字只能是5,有1種選法，由于5已用過，又不可能是0,所以千位上數(shù)有P18種選法,已用過2個數(shù)，所以百位、十位上的數(shù)有P28種選法。所以符合題意的個數(shù)為：

1×P18×P28＝448第18頁，共85頁，2023年，2月20日，星期五例4、用0、1、2、3、4、5六個數(shù)字，可以組成多少個沒有重復(fù)數(shù)字的三位偶數(shù)？1.個位為0,十位為1、2、3、4、5中的一個，百位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有1×P15×P142.個位為2,百位為1、3、4、5中的一個，十位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有1×P14×P143.個位為4,百位為1、2、3、5中的一個，十位為剩下的四個數(shù)字中的一個，所以這樣的偶數(shù)共有1×P14×P14所以符合題意的個數(shù)為20＋16＋16＝52第19頁，共85頁，2023年，2月20日，星期五例5、

8位同學(xué)排成相等的兩行，要求某兩位同學(xué)必須排在前排，有多少種排法？這兩個同學(xué)排在前排4個位置的排列數(shù)是P24，其它同學(xué)在余下的6個位置排的排列數(shù)是6！，所以符合題意的個數(shù)為P24×6！＝12×720＝8640。第20頁，共85頁，2023年，2月20日，星期五例6、某車站有編號為1到6的6個入口處，每個入口處每次只能進一人，問一個小組4人進站的方案有幾種？第一個人有6種方案，第二個人有7種方案，因為他選擇和第一個人相同入口處時，還有前后之分……9*8*7*6=3024

o︱

︱o︱

︱o︱o在兩個入口之間加一個標志︱，共5個無區(qū)別的標志，問題歸結(jié)為9個元素中有5個無區(qū)別的元素，4個不同元素的排列數(shù)。所以4個人進站的方案數(shù)有：9！/5！＝9*8*7*6=3024第21頁，共85頁，2023年，2月20日，星期五相異元素的可重復(fù)排列從n個不同元素中取出r個元素的可重復(fù)的排列種數(shù)為nr.93=729例7．由數(shù)字1,2,3,…,9共能組成多少個三位數(shù)？第22頁，共85頁，2023年，2月20日，星期五相異元素的循環(huán)排列

n個不同元素不分首尾排成一個圓圈，稱為循環(huán)排列。其排列數(shù)為n!/n=(n-1)!。

如1,2,3三個數(shù)的循環(huán)排列只有１２３，１３２二種。第23頁，共85頁，2023年，2月20日，星期五例8．在圓形花壇外側(cè)擺放８盆菊花和４盆蘭花，要求蘭花不能相鄰擺放，一共有多少種擺法？８盆菊花擺成一周的排列方法有n1=７！４盆蘭花插入８個空中的排列總數(shù)有n2=P４８=8!/4!擺放總數(shù)為n=n1*n2=8467200第24頁，共85頁，2023年，2月20日，星期五例9．有男女各五個人，其中有３對是夫妻，沿圓桌就座，若每對夫妻都坐在相鄰的位置，問有多少種坐法？設(shè)３對夫妻分別為Ａ和a,Ｂ和b,Ｃ和c，先讓Ａ，Ｂ，Ｃ三人和另外４個人沿圓桌就座的方法為６！種．又對上述每種坐法，a坐在Ａ的鄰座的方式有左右兩種，b,c也如此．所以共有６！＊２＊２＊２＝５７６０種．第25頁，共85頁，2023年，2月20日，星期五不全相異元素的排列如果在n個元素中，有n1個元素彼此相同，有n2個元素彼此相同，…,又有nm個元素彼此相同，若n1+n2+…+nm=n，則這n個元素的全排列叫做不全相異元素的全排列，其排列數(shù)為:n!/(n1!*n2!*…*nm!).若n1+n2+…+nm=r<n，則這n個元素的全排列叫做不全相異元素的選排列，其排列數(shù)為:prn/(n1!*n2!*…*nm!).第26頁，共85頁，2023年，2月20日，星期五例10、將N個紅球和M個黃球排成一行。如:N=2,M=3可得到10種排法。問題:當N=4,M=3時有

種不同排法?7!/(4!*3!)=35NOIP2002

第27頁，共85頁，2023年，2月20日，星期五例11、把兩個紅球、一個藍球和一個白球放到十個編號不同的盒子中去，有多少種方法？排列數(shù)為p410/(2!*1!*1!)＝2520第28頁，共85頁，2023年，2月20日，星期五生成排列的算法下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個數(shù)的全部可能的排列（不一定按升序輸出）。

例如，輸入3，則應(yīng)該輸出（每行輸出5個排列）：

123132213231321312

求全排列(06年初賽題)第29頁，共85頁，2023年，2月20日，星期五vari,n,k:integer;a:array[1..10]ofinteger;count:longint;procedureperm(

k:integer);varj,p,t:integer;begin

if()thenbegin();forp:=1tokdowrite(a[p]:1);write('');if()thenwriteln;exit;end;

forj:=ktondobegint:=a[k];a[k]:=a[j];a[j]:=t;perm(k+1);t:=a[k];()

endend;beginwriteln('Entryn:');read(n);count:=0;fori:=1tondoa[i]:=i;()end.perm(1)K=ninc(count)countmod5=0a[k]:=a[j];a[j]:=t;123

132

213

231

321

312第30頁，共85頁，2023年，2月20日，星期五算法過程:用數(shù)組：a:array[1..r]ofinteger;表示排列;初始化時，a[i]:=i(i=1,2,…r);設(shè)中間的某一個排列為a[1],a[2],…，a[r]，則求出下一個排列的算法為：①從后面向前找，直到找到一個順序為止（設(shè)下標為j-1,則a[j-1]<a[j]）②從a[j]～a[r]中，找出一個比a[j-1]大的最小元素a[k]③將a[j-1]與a[k]交換④將a[j]，a[j+1]……a[r]由小到大排序。

問題描述:用生成法求出1，2，…，r的全排列(r<=8).{1999年提高組}第31頁，共85頁，2023年，2月20日，星期五constr=7;varn,i,s,k,j,i1,t:intger;a:array[1..r]ofinteger;procedureprint1;varik:integer;beginforik:=1tordowrite(a[ik]:8);writeln;endbeginfori:=1tordo_____________;print1;{輸出第一個排列}s:=1;fori:=2tordos:=s*i;{總排列數(shù)為r!}s:=s-1;{還需生成s-1個排列}fori:=______

____do

begin

j:=r;while______

_______doj:=j-1;k:=j;fori1:=j+1tordoif_____________thenk:=i1;

t:=a[j-1];a[j-1]:=a[k];a[k]:=t;fori1:=jtor-1dofork:=i1+1tordoif_______________thenbegint:=a[i1];a[i1]:=a[k];a[k]:=t;end;print1;

end;end.a[i]:=i

1tosa[j-1]>a[j](a[i1]>a[j-1])and(a[i1]<a[k])a[i1]>a[k]132541345213425第32頁，共85頁，2023年，2月20日，星期五【問題描述】

人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個非常大的數(shù)字告訴人類科學(xué)家，科學(xué)家破解這個數(shù)字的含義后，再把一個很小的數(shù)字加到這個大數(shù)上面，把結(jié)果告訴火星人，作為人類的回答。火星人用一種非常簡單的方式來表示數(shù)字——掰手指。火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為1，2，3……。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數(shù)的。一個火星人用一個人類的手演示了如何用手指計數(shù)。如果把五根手指—拇指、食指、中指、無名指和小指分別編號為1，2，3，4和5，當它們按正常順序排列時，形成了5位數(shù)12345，當你交換無名指和小指的位置時，會形成5位數(shù)12354，當你把五個手指的順序完全顛倒時，會形成54321，在所有能夠形成的120個5位數(shù)中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指時能夠形成的6個3位數(shù)和它們代表的數(shù)字：三進制數(shù)123132213231312321代表的數(shù)字123456火星人（04年普及組）第33頁，共85頁，2023年，2月20日，星期五現(xiàn)在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學(xué)家會告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個結(jié)果不會超出火星人手指能表示的范圍。【輸入文件】輸入文件martian.in包括三行，第一行有一個正整數(shù)N，表示火星人手指的數(shù)目（1<=N<=10000）。第二行是一個正整數(shù)M，表示要加上去的小整數(shù)（1<=M<=100）。下一行是1到N這N個整數(shù)的一個排列，用空格隔開，表示火星人手指的排列順序。【輸出文件】輸出文件martian.out只有一行，這一行含有N個整數(shù)，表示改變后的火星人手指的排列順序。每兩個相鄰的數(shù)中間用一個空格分開，不能有多余的空格。【樣例輸入】5312345【樣例輸出】12453【數(shù)據(jù)規(guī)模】對于30%的數(shù)據(jù)，N<=15；對于60%的數(shù)據(jù)，N<=50；對于全部的數(shù)據(jù)，N<=10000；第34頁，共85頁，2023年，2月20日，星期五varn,m,i,ss,j,k,temp:integer;min:longint;a:array[1..10000]ofinteger;beginreadln(n);readln(m);fori:=1tondoread(a[i]);whilem>0do{一次循環(huán)產(chǎn)生下一個排列}beginj:=n;while(j>1)and(a[j]<a[j-1])doj:=j-1;{從右到左尋找出a[j]>a[j-1]}min:=a[j];k:=j;fori:=jtondoif(a[i]>a[j-1])and(a[i]<min)thenbegink:=i;min:=a[i];end;{從a[j]到a[n],找出一個比a[j-1]大的最小值}temp:=a[j-1];a[j-1]:=a[k];a[k]:=temp;{交換}第35頁，共85頁，2023年，2月20日，星期五

fori:=jton-1dobeginss:=i;fork:=i+1tondoifa[ss]>a[k]thenss:=k;ifss<>ithenbegintemp:=a[i];a[i]:=a[ss];a[ss]:=temp;end;end;{在j到n中，從小到大排列}m:=m-1;end;fori:=1tondowrite(a[i],'');end.531234512354

124531243512453第36頁，共85頁，2023年，2月20日，星期五組合的定義數(shù)學(xué)上，把若干元素，不論次序并成一組，叫做組合。如果兩個組合中，至少有一個元素不同，它們就被認為是不同的組合。abc,abd第37頁，共85頁，2023年，2月20日，星期五相異元素不重復(fù)的組合設(shè)從n個不同的元素中，取出m個不同元素，不考慮順序并成一組，叫作從n個不同的元素中，取出m個不同元素的一個組合。如：寫出從a,b,c,d四個元素中，任取三個元素的所有組合。abc,abd,acd,bcd從n個不同的元素中，取出m個不同元素的組合數(shù)記為Cmn;則有Cmn＝Pmn/m!=n!/m!(n-m)!規(guī)定C0n=1abc,bac,cab,acb,bca,cba第38頁，共85頁，2023年，2月20日，星期五例1、八年級6個班進行排球比賽，每班的排球隊要與其他5個班分別比賽一場，求共要進行多少場比賽？C26＝P26/2!=6*5/2*1=15第39頁，共85頁，2023年，2月20日，星期五例2、平面上有n個點且無三點或三點以上共線，任意兩點可以連成一條直線，一共能連成多少條直線？

C2n＝n*(n-1)/2第40頁，共85頁，2023年，2月20日，星期五例3、某班第一組有10名同學(xué)，第二組有8名同學(xué)，現(xiàn)要求每組選出2名學(xué)生代表參加座談會，有多少種選法？C210×C28＝1260第41頁，共85頁，2023年，2月20日，星期五例4.一元、二元、五元、十元人民幣各一張，一共可以組成多少種不同的幣值？

C14＋C24＋C34＋C44＝4＋6＋4＋1＝15第42頁，共85頁，2023年，2月20日，星期五例5、5年級有8個班，六年級有6個班，先分別舉行各年級的籃球賽，采用單循環(huán)制，然后由兩個年級的第一名爭奪冠軍，共需要比賽多少場？

C28＋C26+1=8*7/2+6*5/2+1=28+15+1=44第43頁，共85頁，2023年，2月20日，星期五例6：某班第一組有10名同學(xué)，其中有4名女同學(xué)，現(xiàn)要求選出3名學(xué)生代表,其中至少有一名女同學(xué)去參加座談會，有多少種選法？

代表中有1名女同學(xué)的選法為C14×C26種，

代表中有2名女同學(xué)的選法為C24×C16種，

代表中有3名女同學(xué)的選法為C34種，C14×C26＋C24×C16＋C34＝100第44頁，共85頁，2023年，2月20日，星期五例7、欲登上第10級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有()。

第45頁，共85頁，2023年，2月20日，星期五例8、∠A的一邊AB上有4個點，另一邊AC上有5個點，連同∠A的頂點共10個點，以這些點為頂點，可以構(gòu)成_____個三角形.90第46頁，共85頁，2023年，2月20日，星期五例9、平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同三角形？（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+210=751第47頁，共85頁，2023年，2月20日，星期五例10、平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形?（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第48頁，共85頁，2023年，2月20日，星期五

例11、10名劃船運動員中，3人只會劃左舷，2人只會劃右舷，5人左右舷都會劃，從中選6人，平均分在左、右舷，共有多少種不同的選法？

1.會劃左舷的全劃左舷：2.派一個全能劃左舷：3.派二個全能劃左舷：4.派三個全能劃左舷：675第49頁，共85頁，2023年，2月20日，星期五例12、小陳現(xiàn)有2個任務(wù)A，B要完成，每個任務(wù)分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務(wù)的b1步驟開始做，當恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有

種。(2009年p)70第50頁，共85頁，2023年，2月20日，星期五排列組合+加法原理:B任務(wù)中的b1一定做，而且肯定是第一個做的。除了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種。加起來1+4+10+20+35=70。b2a1a2a3a1b2

a2a3a1a2b2a3a1a2a3b2

第51頁，共85頁，2023年，2月20日，星期五例13、袋中有已編號的20個球，其中1－10號是紅球，11－20號是白球，每取得一個紅球得2分，取得一個白球得3分，若取得若干個球，共得20分，有多少種不同取法？2x+3y=20,y必是偶數(shù)，所以y=0,2,4,6；相應(yīng)地x=10,7,4,1；

C010×C1010＋C210×C710＋C410×C410

＋C610×C110

＝51601第52頁，共85頁，2023年，2月20日，星期五例14、從1－300之間任取3個不同的數(shù)，使得這3個數(shù)的和恰好被3除盡，有多少種方法？被3除所得的余數(shù)不外乎：0，1，2。所以可把1－300之間的數(shù)分成三組：

A＝{1,4,7,…,298}B＝{2,5,8,…,299}C＝{3,6,9,…,300}

三個數(shù)同屬于集合A，有C3100種，三個數(shù)同屬于集合B，有C3100種，三個數(shù)同屬于集合C，有C3100種，三個數(shù)分屬于集合A，B，C，有1003種。加起來等于

1485100種。第53頁，共85頁，2023年，2月20日，星期五例15、若將一個正整數(shù)化為二進制數(shù)，在此二進制數(shù)中，我們將數(shù)字0的個數(shù)多于數(shù)字1的個數(shù)的這類二進制數(shù)稱為A類數(shù)。例如：（24）10=（11000）2

其中1的個數(shù)為2，0的個數(shù)為3，則稱此數(shù)為A類數(shù)；請你求出1～112之中（包括1與112），全部A類數(shù)的個數(shù)。（112）10=（1110000）2可根據(jù)二進制數(shù)的前綴來分類。第54頁，共85頁，2023年，2月20日，星期五111××××：這類數(shù)中A類數(shù)只有一個，即1110000110××××：這類數(shù)中A類數(shù)個數(shù)為：

C44＋C34＝510×××××：這類數(shù)中A類數(shù)個數(shù)為：

C55＋C45＋C35

＝160××××××：位數(shù)不確定，需對位數(shù)進行討論。第55頁，共85頁，2023年，2月20日，星期五1位數(shù)，即1,不是A類數(shù)，2位數(shù)，即1×，10和11都不是A類數(shù)，3位數(shù)，即1××，只有100一個，4位數(shù)，即1×××，只有1000一個，5位數(shù)，即1××××，A類數(shù)個數(shù)有C44＋C34＝5,6位數(shù)，即1×××××，A類數(shù)個數(shù)有C55＋C45＝6,1＋5＋16＋（1＋1＋5＋6）＝35第56頁，共85頁，2023年，2月20日，星期五例16、某城市有4條東西街道和6條南北的街道，街道之間的間距相同。若規(guī)定只能向東或向北兩個方向沿圖中路線前進，則從M到N有多少種不同的走法?(2007年p)MN（一）從M到N必須向上走三步，向右走五步，共走八步。（二）每一步是向上還是向右，決定了不同的走法。（三）事實上，當把向上的步驟決定后，剩下的步驟只能向右。從而，任務(wù)可敘述為：從八個步驟中選出哪三步是向上走，就可以確定走法數(shù)。

∴本題答案為56。第57頁，共85頁，2023年，2月20日，星期五相異元素的可重復(fù)組合設(shè)從n個不同的元素中，取出m個不同元素，若允許這個元素可以重復(fù)使用，也允許m>n，則把這樣的組合稱為重復(fù)組合，其組合數(shù)記為Hmn。

Hmn=Cmn+m-1

如1,2,3,4,四個數(shù)字中取三個，允許重復(fù)的組合有以下20種：

111,122,134,224,333112,123,144,233,334113,124,222,234,344114,133,223,244,444第58頁，共85頁，2023年，2月20日，星期五組合的生成算法從1,2,3,…,n共n個數(shù)中任取m個數(shù)，請輸出所有組合并計算組合數(shù)。varn,m,i,k,s:integer;a,b:array[0..100]ofinteger;beginreadln(n,m);fori:=1tomdobegina[i]:=i;b[i]:=

;end;k:=m;s:=0;repeatif

thenbegins:=s+1;fori:=1tomdowrite(a[i]);write('');end;ifa[k]<b[k]thenbegin

;ifk<mthenfork:=k+1tomdo

;endelse

;untilk=0;writeln;writeln('s=',s);end.n-m+ik=ma[k]:=a[k]+1a[k]:=a[k-1]+1k:=k-1第59頁，共85頁，2023年，2月20日，星期五Jam的計數(shù)法【問題描述】Jam是個喜歡標新立異的科學(xué)怪人。他不使用阿拉伯數(shù)字計數(shù)，而是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為Jam數(shù)字。在Jam數(shù)字中，每個字母互不相同，而且從左到右是嚴格遞增的。每次，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”，則U<V，且不存在Jam數(shù)字P，使U<P<V）。你的任務(wù)是：對于從文件讀入的一個Jam數(shù)字，按順序輸出緊接在后面的5個Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個就輸出幾個。第60頁，共85頁，2023年，2月20日，星期五

【輸入文件】輸入文件counting.in有2行，第1行為3個正整數(shù)，用一個空格隔開：stw（其中s為所使用的最小的字母的序號，t為所使用的最大的字母的序號。w為數(shù)字的位數(shù)，這3個數(shù)滿足：1≤s<t≤26,2≤w≤t-s）第2行為具有w個小寫字母的字符串，為一個符合要求的Jam數(shù)字。【輸出文件】輸出文件counting.out最多為5行，為緊接在輸入的Jam數(shù)字后面的5個Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個就輸出幾個。每行只輸出一個Jam數(shù)字，是由w個小寫字母組成的字符串，不要有多余的空格。【輸入樣例】2105bdfij【輸出樣例】bdghibdghjbdgijbdhijbefgh第61頁，共85頁，2023年，2月20日，星期五vari,j,s,t,w,n:longint;st:string;a:array[0..30]ofinteger;beginreadln(s,t,w);readln(st);{輸入起始字符串}fori:=1towdoa[i]:=ord(st[i])-(ord('a')+s)+2;{將字符串轉(zhuǎn)變?yōu)閿?shù)字串}a[0]:=0;n:=0;{控制開關(guān)變0和生成個數(shù)清0}while(a[0]=0)and(n<5)dobegini:=w;while(a[i]=t-s+1-w+i)and(i>0)doi:=i-1;inc(a[i]);forj:=i+1towdoa[j]:=a[j-1]+1;{產(chǎn)生下一個組合}ifa[0]<>0thenbeginhalt;endelsebeginfori:=1towdowrite(chr(ord('a')+a[i]+s-2));writeln;n:=n+1;{個數(shù)加1}end;end;end.2105bdfij先轉(zhuǎn)換：98-(97+2)+2=113589{初始組合}i=5時，t-s-w+i+1=10-2-5+5+1=9a[5]最大可取9產(chǎn)生下一個組合：13678輸出：i=1時,chr(97+1+2-2)=bbdghi第62頁，共85頁，2023年，2月20日，星期五排列組合題型總結(jié)排列組合問題千變?nèi)f化，解法靈活，條件隱晦，思維抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用題時，除做到：排列組合分清，加乘原理辯明，避免重復(fù)遺漏外，還應(yīng)注意積累排列組合問題得以快速準確求解。第63頁，共85頁，2023年，2月20日，星期五直接法1.特殊元素法

用1，2，3，4，5，6這6個數(shù)字組成無重復(fù)的四位數(shù)，試求滿足下列條件的四位數(shù)各有多少個（1）數(shù)字1不排在個位和千位;（2）數(shù)字1不在個位，數(shù)字6不在千位。分析：（1）個位和千位有5個數(shù)字可供選擇，其余2位有四個可供選擇，由乘法原理：=240

特殊元素，優(yōu)先處理；特殊位置，優(yōu)先考慮。第64頁，共85頁，2023年，2月20日，星期五2.特殊位置法

（2）當1在千位時余下三位有=60，1不在千位時，千位有種選法，個位有種，余下的有，共有

=192,所以總共有192+60=252第65頁，共85頁，2023年，2月20日，星期五間接法當直接法求解類別比較大時，應(yīng)采用間接法。如上例中（2）可用間接法

第66頁，共85頁，2023年，2月20日，星期五有五張卡片，它的正反面分別寫0與1，2與3，4與5，6與7，8與9，將它們?nèi)我馊龔埐⑴欧旁谝黄鸾M成三位數(shù)，共可組成多少個不同的三位數(shù)？

分析：此例正面求解需考慮0與1卡片用與不用，且用此卡片又分使用0與使用1，類別較復(fù)雜，因而可使用間接計算：任取三張卡片可以組成不同的三位數(shù)個，其中0在百位的有個，這是不合題意的。故共可組成不同的三位數(shù)=432（個）.第67頁，共85頁，2023年，2月20日，星期五

8位同學(xué)排成一行，要求某兩位同學(xué)互不相鄰，有多少種排法？8位同學(xué)排成一行的總數(shù)是8！把排在一起的的兩個同學(xué)看成一個人的排列總數(shù)是7！因為排在一起的兩個同學(xué)的位置可以互換，所以兩位同學(xué)排在一起的排列數(shù)是2×7！所以符合題意的個數(shù)為8！－2×7！＝30240第68頁，共85頁，2023年，2月20日，星期五正方體8個頂點中取出4個，可組成多少個四面體?所求問題的方法數(shù)=任意選四點的組合數(shù)-共面四點的方法數(shù)，∴-12=70-12=58個。第69頁，共85頁，2023年，2月20日，星期五插空法在一個含有8個節(jié)目的節(jié)目單中，臨時插入兩個歌唱節(jié)目，且保持原節(jié)目順序，有多少種插入方法？原有的8個節(jié)目中含有9個空檔，插入一個節(jié)目后，空檔變?yōu)?0個，故有=90中插入方法。第70頁，共85頁，2023年，2月20日，星期五

8位同學(xué)排成一行，其中有4位女同學(xué)，要求女同學(xué)不相鄰，有多少種排法？四位男同學(xué)排成一行的總數(shù)是4！，在他們首尾兩個位置和他們兩兩之間的位置（共5個）分別插入一個女同學(xué)的排列數(shù)是A45＝120，所以符合題意的個數(shù)是4！×120＝2880第71頁，共85頁，2023年，2月20日，星期五馬路上有編號為l，2，3，……，10十個路燈，為節(jié)約用電又看清路面，可以把其中的三只燈關(guān)掉，但不能同時關(guān)掉相鄰的兩只或三只，在兩端的燈也不能關(guān)掉的情況下，求滿足條件的關(guān)燈方法共有多少種?

關(guān)掉的燈不能相鄰，也不能在兩端。又因為燈與燈之間沒有區(qū)別，因而問題為在7盞亮著的燈形成的不包含兩端的6個空中選出3個空放置熄滅的燈。∴共=20種方法。

第72頁，共85頁，2023年，2月20日，星期五捆綁法當需排元素中有必須相鄰的元素時，宜用捆綁法。

4名男生和3名女生共坐一排，男生必須排在一起的坐法有多少種？分析：先將男生捆綁在一起看成一個大元素與女生全排列有種排法，而男生之間又有種排法，由乘法原理滿足條件的排法有：×=576第73頁，共85頁，2023年，2月20日，星期五四個不同的小球全部放入三個不同的盒子中，若使每個盒子不空，則不同的放法有

種。一定有兩個球放在同一個盒子中．第74頁，共85頁，2023年，2月20日，星期五某市植物園要在30天內(nèi)接待20所學(xué)校的學(xué)生參觀，但每天只能安排一所學(xué)校，其中有一所學(xué)校人數(shù)較多，要安排連續(xù)參觀2天，其余只參觀一天，則植物園30天內(nèi)不同的安排方法有（）.注意連續(xù)參觀2天，即需把30天中的連續(xù)兩天捆綁看成一天作為一個整體來選有，其余的就是19所學(xué)校選28天進行排列。第75頁，共85頁，2023年，2月20日，星期五書架上有四本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這四本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有（）種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有（）種擺法。（2008年p）第76頁，共85頁，2023年，2月20日，星期五閘板法名額分配或相同物品的分配問題，適宜采用閘板法.

某校準備組建一個由12人組成的籃球隊，這12個人由8個班的學(xué)生組成，每班至少一人，名額分配方案共

種。分析：此例的實質(zhì)是12個名額分配給8個班，每班至少一個名額，可在12個名額中的11個空當中插入7塊閘板，一種插法對應(yīng)一種名額的分配方式，故有種。第77頁，共85頁，2023年，2月20日，星期五若m,n∈N,m≦n，把n寫成m個自然數(shù)之和，如：m＝3,n＝5時，5＝1＋1＋3＝1＋3＋1＝3＋1＋1＝2＋2＋1＝2＋1＋2＝1＋2＋2.問共有多少種表示法？5＝1＋1＋（1＋1＋1）＝1＋（1＋1＋1）＋1＝（1＋1＋1）＋1＋1＝（1＋1）＋（1＋1）＋1＝（1＋1）＋1＋（1＋1）＝1＋（1＋1）＋（1＋1）對n=1+1+1+…+1有幾種加括號的方法，也就是在n-1個加號中，保留m-1個加號，將其余的各部分元素分別加起來。

Cm-1n-1第78頁，共85頁，2023年，2月20日，星期五平均分堆6本不同的書平均分成三堆，有多少種不同的方法？

分析：分出三堆書（a1,a2）,(a3,a4)，（a5,a6）,由順序不同可以有=6種，而這6種分法只算一種分堆方式