排列組合專(zhuān)題

排列組合專(zhuān)題第1頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月1.加法原理:

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

如果完成一項(xiàng)工作有兩個(gè)連續(xù)的步驟A和B,在步驟A中有m種不同的方式,在步驟B中有n種不同的方式,則完成這項(xiàng)工作的總的方法有m*n種.第2頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例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種.第3頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例2、一個(gè)三位數(shù)，如果它的每一位數(shù)字都不小于另一個(gè)三位數(shù)對(duì)應(yīng)數(shù)位上的數(shù)字，就稱(chēng)它“吃掉”后一個(gè)三位數(shù)，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位數(shù)共有多少個(gè)？百位上有5、6、7、8、9五種選擇，十位上有8、9兩種選擇，個(gè)位上有7，8，9三種選擇，所以共有5×2×3=30（個(gè)）三位數(shù)。第4頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例3、如圖，一方形花壇分成編號(hào)為①，②，③，④四塊，現(xiàn)有紅、黃、藍(lán)、紫四種顏色的花供選種，要求每塊只種一種顏色的花，且相鄰的兩塊種不同顏色的花。如果編號(hào)為①的已經(jīng)種上紅色花，那么其余三塊不同的種法有

種。21

編號(hào)為②的有三種選擇，對(duì)于編號(hào)為③的，可以分成以下二類(lèi)：1、若編號(hào)為④的與編號(hào)為②的同色，則編號(hào)為③的有三種選擇。這種情況下共有3×3種方案。2、若編號(hào)為④的與編號(hào)為②的不同色，則編號(hào)為③的有二種選擇，編號(hào)為④的有二種選擇。這種情況下共有3×2×2種方案。第5頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例4、用紅、黃、綠、藍(lán)、黑五種顏色涂在如下圖所示的ABCDE五區(qū)域，顏色可重復(fù)使用，但同色不相鄰，涂法有幾種？

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

第6頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例5、在一塊并排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟，為有利于作物生長(zhǎng)，要求A，B兩種作物的間隔不少于6壟，不同的選法共有______種。分析：采取分類(lèi)的方法。第一類(lèi)：A在第一壟，B有3種選擇；第二類(lèi)：A在第二壟，B有2種選擇；第三類(lèi)：A在第三壟，B有一種選擇，同理A、B位置互換，共12種。第7頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例6、某小組有10人，每人至少會(huì)英語(yǔ)和日語(yǔ)的一門(mén)，其中8人會(huì)英語(yǔ)，5人會(huì)日語(yǔ)，從中選出會(huì)英語(yǔ)與會(huì)日語(yǔ)的各1人，有多少種不同的選法?

由于8+5＝13＞10，所以10人中必有3人既會(huì)英語(yǔ)又會(huì)日語(yǔ)。（5+2+3）所以可分三類(lèi)：

5×2+5×3+2×3=31第8頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例7、在所有的三位數(shù)中，有且只有兩個(gè)數(shù)字相同的三位數(shù)共有多少個(gè)?

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

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

第9頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例8、求正整數(shù)1400的正因數(shù)的個(gè)數(shù)．因?yàn)槿魏我粋€(gè)正整數(shù)的任何一個(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)=24．第10頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例9、從1到300的自然數(shù)中，完全不含有數(shù)字3的有多少個(gè)？將0到299的整數(shù)都看成三位數(shù)，其中數(shù)字3不出現(xiàn)的，百位數(shù)字可以是0，1或2三種情況。十位數(shù)字與個(gè)位數(shù)字均有九種，因此除去0共有3×9×9－1=242(個(gè))．第11頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例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種寫(xiě)法，所以，根據(jù)乘法原理，由這九個(gè)數(shù)字組成的四位數(shù)個(gè)數(shù)為9×9×9×9＝6561。

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

1.所含元素不全相同

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

第14頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月一般地，從n個(gè)不同的元素中取出r個(gè)元素的選排列數(shù)用表示，則＝n!/(n-r)!第15頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例１．全國(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=182第16頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月當(dāng)n=r時(shí),叫做n個(gè)不同元素的全排列．n個(gè)不同元素的全排列數(shù)Pnn

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

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

8位同學(xué)排成相等的兩行，要求某兩位同學(xué)必須排在前排，有多少種排法？這兩個(gè)同學(xué)排在前排4個(gè)位置的排列數(shù)是P24，其它同學(xué)在余下的6個(gè)位置排的排列數(shù)是6！，所以符合題意的個(gè)數(shù)為P24×6?。?2×720＝8640。第20頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例6、某車(chē)站有編號(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︱

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

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

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

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

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

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

123132213231321312

求全排列(06年初賽題)第29頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月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頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月算法過(guò)程:用數(shù)組：a:array[1..r]ofinteger;表示排列;初始化時(shí)，a[i]:=i(i=1,2,…r);設(shè)中間的某一個(gè)排列為a[1],a[2],…，a[r]，則求出下一個(gè)排列的算法為：①?gòu)暮竺嫦蚯罢?，直到找到一個(gè)順序?yàn)橹梗ㄔO(shè)下標(biāo)為j-1,則a[j-1]<a[j]）②從a[j]～a[r]中，找出一個(gè)比a[j-1]大的最小元素a[k]③將a[j-1]與a[k]交換④將a[j]，a[j+1]……a[r]由小到大排序。

問(wèn)題描述:用生成法求出1，2，…，r的全排列(r<=8).{1999年提高組}第31頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月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;{輸出第一個(gè)排列}s:=1;fori:=2tordos:=s*i;{總排列數(shù)為r!}s:=s-1;{還需生成s-1個(gè)排列}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頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月【問(wèn)題描述】

人類(lèi)終于登上了火星的土地并且見(jiàn)到了神秘的火星人。人類(lèi)和火星人都無(wú)法理解對(duì)方的語(yǔ)言，但是我們的科學(xué)家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個(gè)非常大的數(shù)字告訴人類(lèi)科學(xué)家，科學(xué)家破解這個(gè)數(shù)字的含義后，再把一個(gè)很小的數(shù)字加到這個(gè)大數(shù)上面，把結(jié)果告訴火星人，作為人類(lèi)的回答。火星人用一種非常簡(jiǎn)單的方式來(lái)表示數(shù)字——掰手指。火星人只有一只手，但這只手上有成千上萬(wàn)的手指，這些手指排成一列，分別編號(hào)為1，2，3……?；鹦侨说娜我鈨筛种付寄茈S意交換位置，他們就是通過(guò)這方法計(jì)數(shù)的。一個(gè)火星人用一個(gè)人類(lèi)的手演示了如何用手指計(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ù)123132213231312321代表的數(shù)字123456火星人（04年普及組）第33頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月現(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è)排列，用空格隔開(kāi)，表示火星人手指的排列順序。【輸出文件】輸出文件martian.out只有一行，這一行含有N個(gè)整數(shù)，表示改變后的火星人手指的排列順序。每?jī)蓚€(gè)相鄰的數(shù)中間用一個(gè)空格分開(kāi)，不能有多余的空格?！緲永斎搿?312345【樣例輸出】12453【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，N<=15；對(duì)于60%的數(shù)據(jù)，N<=50；對(duì)于全部的數(shù)據(jù)，N<=10000；第34頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月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)生下一個(gè)排列}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],找出一個(gè)比a[j-1]大的最小值}temp:=a[j-1];a[j-1]:=a[k];a[k]:=temp;{交換}第35頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月

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

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

C14＋C24＋C34＋C44＝4＋6＋4＋1＝15第42頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例5、5年級(jí)有8個(gè)班，六年級(jí)有6個(gè)班，先分別舉行各年級(jí)的籃球賽，采用單循環(huán)制，然后由兩個(gè)年級(jí)的第一名爭(zhēng)奪冠軍，共需要比賽多少場(chǎng)？

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

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

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

代表中有3名女同學(xué)的選法為C34種，C14×C26＋C24×C16＋C34＝100第44頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例7、欲登上第10級(jí)樓梯，如果規(guī)定每步只能跨上一級(jí)或兩級(jí)，則不同的走法共有()。

第45頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例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è)三角形.90第46頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例9、平面上有三條平行直線(xiàn)，每條直線(xiàn)上分別有7，5，6個(gè)點(diǎn)，且不同直線(xiàn)上三個(gè)點(diǎn)都不在同一條直線(xiàn)上。問(wèn)用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同三角形？（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頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例10、平面上有三條平行直線(xiàn)，每條直線(xiàn)上分別有7，5，6個(gè)點(diǎn)，且不同直線(xiàn)上三個(gè)點(diǎn)都不在同一條直線(xià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=2250第48頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月

例11、10名劃船運(yùn)動(dòng)員中，3人只會(huì)劃左舷，2人只會(huì)劃右舷，5人左右舷都會(huì)劃，從中選6人，平均分在左、右舷，共有多少種不同的選法？

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

種。(2009年p)70第50頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月排列組合+加法原理:B任務(wù)中的b1一定做，而且肯定是第一個(gè)做的。除了b1外，第一類(lèi)：完成A任務(wù)只有1種。第二類(lèi)：完成A任務(wù)和b2有C(4,1)=4種。第三類(lèi)：完成A任務(wù)和b2、b3有C(5,2)=10種。第四類(lèi)：完成A任務(wù)和b2、b3、b4有C(6,3)=20種。第五類(lèi)：完成A任務(wù)和b2、b3、b4、b5有C(7,4)=35種。加起來(lái)1+4+10+20+35=70。b2a1a2a3a1b2

a2a3a1a2b2a3a1a2a3b2

第51頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例13、袋中有已編號(hào)的20個(gè)球，其中1－10號(hào)是紅球，11－20號(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；

C010×C1010＋C210×C710＋C410×C410

＋C610×C110

＝51601第52頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例14、從1－300之間任取3個(gè)不同的數(shù)，使得這3個(gè)數(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}

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

1485100種。第53頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月例15、若將一個(gè)正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字0的個(gè)數(shù)多于數(shù)字1的個(gè)數(shù)的這類(lèi)二進(jìn)制數(shù)稱(chēng)為A類(lèi)數(shù)。例如：（24）10=（11000）2

其中1的個(gè)數(shù)為2，0的個(gè)數(shù)為3，則稱(chēng)此數(shù)為A類(lèi)數(shù)；請(qǐng)你求出1～112之中（包括1與112），全部A類(lèi)數(shù)的個(gè)數(shù)。（112）10=（1110000）2可根據(jù)二進(jìn)制數(shù)的前綴來(lái)分類(lèi)。第54頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月111××××：這類(lèi)數(shù)中A類(lèi)數(shù)只有一個(gè)，即1110000110××××：這類(lèi)數(shù)中A類(lèi)數(shù)個(gè)數(shù)為：

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

C55＋C45＋C35

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

∴本題答案為56。第57頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月相異元素的可重復(fù)組合設(shè)從n個(gè)不同的元素中，取出m個(gè)不同元素，若允許這個(gè)元素可以重復(fù)使用，也允許m>n，則把這樣的組合稱(chēng)為重復(fù)組合，其組合數(shù)記為Hmn。

Hmn=Cmn+m-1

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

111,122,134,224,333112,123,144,233,334113,124,222,234,344114,133,223,244,444第58頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月組合的生成算法從1,2,3,…,n共n個(gè)數(shù)中任取m個(gè)數(shù)，請(qǐng)輸出所有組合并計(jì)算組合數(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頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月Jam的計(jì)數(shù)法【問(wèn)題描述】Jam是個(gè)喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計(jì)數(shù)，而是使用小寫(xiě)英文字母計(jì)數(shù)，他覺(jué)得這樣做，會(huì)使世界更加豐富多彩。在他的計(jì)數(shù)法中，每個(gè)數(shù)字的位數(shù)都是相同的（使用相同個(gè)數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱(chēng)為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”，則U<V，且不存在Jam數(shù)字P，使U<P<V）。你的任務(wù)是：對(duì)于從文件讀入的一個(gè)Jam數(shù)字，按順序輸出緊接在后面的5個(gè)Jam數(shù)字，如果后面沒(méi)有那么多Jam數(shù)字，那么有幾個(gè)就輸出幾個(gè)。第60頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月

【輸入文件】輸入文件counting.in有2行，第1行為3個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：stw（其中s為所使用的最小的字母的序號(hào)，t為所使用的最大的字母的序號(hào)。w為數(shù)字的位數(shù)，這3個(gè)數(shù)滿(mǎn)足：1≤s<t≤26,2≤w≤t-s）第2行為具有w個(gè)小寫(xiě)字母的字符串，為一個(gè)符合要求的Jam數(shù)字?！据敵鑫募枯敵鑫募ounting.out最多為5行，為緊接在輸入的Jam數(shù)字后面的5個(gè)Jam數(shù)字，如果后面沒(méi)有那么多Jam數(shù)字，那么有幾個(gè)就輸出幾個(gè)。每行只輸出一個(gè)Jam數(shù)字，是由w個(gè)小寫(xiě)字母組成的字符串，不要有多余的空格?！据斎霕永?105bdfij【輸出樣例】bdghibdghjbdgijbdhijbefgh第61頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月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;{控制開(kāi)關(guān)變0和生成個(gè)數(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)生下一個(gè)組合}ifa[0]<>0thenbeginhalt;endelsebeginfori:=1towdowrite(chr(ord('a')+a[i]+s-2));writeln;n:=n+1;{個(gè)數(shù)加1}end;end;end.2105bdfij先轉(zhuǎn)換：98-(97+2)+2=113589{初始組合}i=5時(shí)，t-s-w+i+1=10-2-5+5+1=9a[5]最大可取9產(chǎn)生下一個(gè)組合：13678輸出：i=1時(shí),chr(97+1+2-2)=bbdghi第62頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月排列組合題型總結(jié)排列組合問(wèn)題千變?nèi)f化，解法靈活，條件隱晦，思維抽象，難以找到解題的突破口。因而在求解排列組合應(yīng)用題時(shí)，除做到：排列組合分清，加乘原理辯明，避免重復(fù)遺漏外，還應(yīng)注意積累排列組合問(wèn)題得以快速準(zhǔn)確求解。第63頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月直接法1.特殊元素法

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

特殊元素，優(yōu)先處理；特殊位置，優(yōu)先考慮。第64頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月2.特殊位置法

（2）當(dāng)1在千位時(shí)余下三位有=60，1不在千位時(shí)，千位有種選法，個(gè)位有種，余下的有，共有

=192,所以總共有192+60=252第65頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月間接法當(dāng)直接法求解類(lèi)別比較大時(shí)，應(yīng)采用間接法。如上例中（2）可用間接法

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

分析：此例正面求解需考慮0與1卡片用與不用，且用此卡片又分使用0與使用1，類(lèi)別較復(fù)雜，因而可使用間接計(jì)算：任取三張卡片可以組成不同的三位數(shù)個(gè)，其中0在百位的有個(gè)，這是不合題意的。故共可組成不同的三位數(shù)=432（個(gè)）.第67頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月

8位同學(xué)排成一行，要求某兩位同學(xué)互不相鄰，有多少種排法？8位同學(xué)排成一行的總數(shù)是8！把排在一起的的兩個(gè)同學(xué)看成一個(gè)人的排列總數(shù)是7！因?yàn)榕旁谝黄鸬膬蓚€(gè)同學(xué)的位置可以互換，所以?xún)晌煌瑢W(xué)排在一起的排列數(shù)是2×7！所以符合題意的個(gè)數(shù)為8?。?×7?。?0240第68頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月正方體8個(gè)頂點(diǎn)中取出4個(gè)，可組成多少個(gè)四面體?所求問(wèn)題的方法數(shù)=任意選四點(diǎn)的組合數(shù)-共面四點(diǎn)的方法數(shù)，∴-12=70-12=58個(gè)。第69頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月插空法在一個(gè)含有8個(gè)節(jié)目的節(jié)目單中，臨時(shí)插入兩個(gè)歌唱節(jié)目，且保持原節(jié)目順序，有多少種插入方法？原有的8個(gè)節(jié)目中含有9個(gè)空檔，插入一個(gè)節(jié)目后，空檔變?yōu)?0個(gè)，故有=90中插入方法。第70頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月

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

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

第72頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月捆綁法當(dāng)需排元素中有必須相鄰的元素時(shí)，宜用捆綁法。

4名男生和3名女生共坐一排，男生必須排在一起的坐法有多少種？分析：先將男生捆綁在一起看成一個(gè)大元素與女生全排列有種排法，而男生之間又有種排法，由乘法原理滿(mǎn)足條件的排法有：×=576第73頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月四個(gè)不同的小球全部放入三個(gè)不同的盒子中，若使每個(gè)盒子不空，則不同的放法有

種。一定有兩個(gè)球放在同一個(gè)盒子中．第74頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月某市植物園要在30天內(nèi)接待20所學(xué)校的學(xué)生參觀(guān)，但每天只能安排一所學(xué)校，其中有一所學(xué)校人數(shù)較多，要安排連續(xù)參觀(guān)2天，其余只參觀(guān)一天，則植物園30天內(nèi)不同的安排方法有（）.注意連續(xù)參觀(guān)2天，即需把30天中的連續(xù)兩天捆綁看成一天作為一個(gè)整體來(lái)選有，其余的就是19所學(xué)校選28天進(jìn)行排列。第75頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月書(shū)架上有四本不同的書(shū)A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這四本書(shū)擺在書(shū)架上，滿(mǎn)足所有黑皮的書(shū)都排在一起的擺法有（）種。滿(mǎn)足A必須比C靠左，所有紅皮的書(shū)要擺放在一起，所有黑皮的書(shū)要擺放在一起，共有（）種擺法。（2008年p）第76頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月閘板法名額分配或相同物品的分配問(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)一種名額的分配方式，故有種。第77頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月若m,n∈N,m≦n，把n寫(xiě)成m個(gè)自然數(shù)之和，如：m＝3,n＝5時(shí)，5＝1＋1＋3＝1＋3＋1＝3＋1＋1＝2＋2＋1＝2＋1＋2＝1＋2＋2.問(wèn)共有多少種表示法？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）對(duì)n=1+1+1+…+1有幾種加括號(hào)的方法，也就是在n-1個(gè)加號(hào)中，保留m-1個(gè)加號(hào)，將其余的各部分元素分別加起來(lái)。

Cm-1n-1第78頁(yè)，課件共85頁(yè)，創(chuàng)作于2023年2月平均分堆6本不同的書(shū)平均分成三堆，有多少種不同的方法？

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