小學(xué)數(shù)學(xué)競賽7-6-計數(shù)方法與技巧綜合

1、計數(shù)方法與技巧綜合7-6.計數(shù)方法與技巧綜合.題庫教師版page 18 of 16知識框架圖7計數(shù)綜合7-6計數(shù)方法與技 巧綜合7- 6-1歸納法7- 6- 2整體法7- 6- 3對應(yīng)法7- 6- 3-1圖形中的對應(yīng)關(guān)系7- 6- 3- 2數(shù)字問題中的對應(yīng)關(guān)系7- 6- 3- 3對應(yīng)與階梯型標(biāo)數(shù)法7- 6- 3- 4不完全對應(yīng)關(guān)系7- 6- 4遞推法教學(xué)目標(biāo)前面在講加法原理、乘法原理、排列組合時已經(jīng)穿插講解了計數(shù)中的一些常用的方法，比如枚舉法、樹 形圖法、標(biāo)數(shù)法、捆綁法、排除法、插板法等等，這里再集中學(xué)習(xí)一下計數(shù)中其他常見的方法，主要有歸納 法、整體法、對應(yīng)法、遞推法.對這些計數(shù)方法與技巧要做

2、到靈活運用.例題精講模塊一、歸納法從條件值較小的數(shù)開始，找出其中規(guī)律，或找出其中的遞推數(shù)量關(guān)系，歸納出一般情況下的數(shù)量關(guān)系.【例1】（難度等級）一條直線分一個平面為兩部分.兩條直線最多分這個平面為四部分.問5條直線最多分這個平面為多少部分 ？【解析】方法一：我們可以在紙上試著畫出1條直線，2條直線，3條直線，時的情形，于是得到下表：直線條數(shù)123456最多可分成的部分政247n1622后一項與前一項的基23456由上表已知5條直線最多可將這個平面分成16個部分，并且不又t知曉，當(dāng)有n條直線時，最多可將平面分成 2+2+3+4+n=n（n.1）+1個部分2方法二：如果已有 k條直線，再增加一條直

3、線，這條直線與前k條直線的交點至多 k個，因而至多被分成k+1段，每一段將原有的部分分成兩個部分，所以至多增加k+1個部分.于是3條直線至多將平面分為4+3=7個部分，4條直線至多將平面分為7+4=11個部分，5條直線至多將平面分為 11+5=16個部分.一般的有k條直線最多將平面分成：1+1+2+k=k（k +1 %個部分，所以五條直線可以分平面為162個部分.【鞏固】(難度等級)平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？【解析】 假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù)，這里 k= 0, 1, 2,ao= 1ai=ao+1 =2a2=

4、ai + 2=4a3=a2 + 3=7a4=a3+4 = 11故5條直線可以把圓分成 16部分，100條直線可以把圓分成 5051部分【例2】(難度等級 派)平面上10個兩兩相交的圓最多能將平面分割成多少個區(qū)域？【解析】先考慮最簡單的情形.為了敘述方便，設(shè)平面上k個圓最多能將平面分割成 akj部分.從圖中可以看出,a1=2, a2=4=2+2M1, a3=8=4+2M2, a4=14=8+2M3,可以發(fā)現(xiàn)ak滿足下列關(guān)系式：ak =ak+2(k -1 ).實際上，當(dāng)平面上的(k-1)個圓把平面分成ak二個區(qū)域時，如果再在平面上出現(xiàn)第k個圓，為了保證劃分平面的區(qū)域盡可能多，新添的第k個圓不能通過

5、平面上前(k-1)個圓之間的交點.這樣，第k個圓與前面(k-1)個圓共產(chǎn)生2M(k-1)個交點，如下圖：而這2 M (k-1)段圓弧中的每一段都將所在的這2M(k1)個交點把第k個圓分成了 2M(k1)段圓弧,區(qū)域一分為二，所以也就是整個平面的區(qū)域數(shù)增加了2M(k-1)個部分.所以，ak=ak+ 2(k-1).那么，aw=ag 2 9=% 2 8 2 9= a7 2 7 2 8 2 9二& 2 1 2 2 . 2 7 2 8 2 9 =2 +2父(1 +2 +7 +8+9 )=92 .故10個圓最多能將平面分成 92部分.【例3】【解析】例410個三角形最多將平面分成幾個部分？設(shè)n個三

6、角形最多將平面分成 an個部分.n =1 時，ai =2 ；n=2時，第二個三角形的每一條邊與第一個三角形最多有2個交點，三條邊與第一個三角形最多有2x3=6 （個）交點.這6個交點將第二個三角形的周邊分成了6段，這6段中的每一段都將原來的每一個部分分成 2個部分，從而平面也增加了6個部分，即a2=2+2x3.n=3時，第三個三角形與前面兩個三角形最多有4父3=12 （個）交點，從而平面也增加了 12個部分，即：a3 =2 2 3 4 3 . 一般地，第n個三角形與前面（n1 ）個三角形最多有2（n _1產(chǎn)3個交點，從而平面也增加2（n_1y（3個 部分，故 an =2+2M3+4M3 + |

7、+2（n 1 產(chǎn)3=2 +2+4 訓(xùn)+2（n 1 ）M3 = 3n23n+2 ;特別地，當(dāng)n =10時，a10 =3父102 +3M10 +2=272 ,即10個三角形最多把平面分成 272個部分.（難度等級）一個長方形把平面分成兩部分，那么3個長方形最多把平面分成多少部分?【解析】一個長方形把平面分成兩部分.第二個長方形的每一條邊至多把第一個長方形的內(nèi)部分成2部分,這樣第一個長方形的內(nèi)部至多被第二個長方形分成五部分.同理，第二個長方形的內(nèi)部至少被第一個長方形分成五部分.這兩個長方形有公共部分（如下圖，標(biāo)有數(shù)字9的部分）.還有一個區(qū)域位于兩個長方形外面，所以兩個長方形至多把平面分成10部分.【

8、小結(jié)】例5【解析】第三個長方形的每一條邊至多與前兩個長方形中的每一個的兩條邊相交，故第一條邊被隔成五條小線段，其中間的三條小線段中的每一條線段都把前兩個長方形內(nèi)部的某一部分一分為二，所以至多增加3M=12個部分.而第三個長方形的4個頂點都在前兩個長方形的外面，至多能增加4個部分.所以三個長方形最多能將平面分成10+12+4=26.n個圖形最多可把平面分成部分?jǐn)?shù)：直線：1+nrim)；2圓：2+nM(n1);三角形：2+3MnM(n1);長方形：2+4MnM(n1).（難度等級派）在平面上畫5個圓和1條直線，最多可把平面分成多少部分？先考慮圓.1個圓將平面分成2個部分.這時增加1個圓，這個圓與原

9、有的 1個圓最多有兩個交點，成為2條弧，每條弧將平面的一部分一分為二，增加了2個部分，所以2個圓最多將平面分成 4個部分.當(dāng)有3個圓時，第3個圓與原有的2個產(chǎn)生4個交點而增加4個部分，所以3個圓最多將平面分成8個部分.同樣的道理，5個圓最多將平面分成 22個部分.再考慮直線.直線與每個圓最多有 2個交點，這樣與5個圓最多有10個交點.它們將直線分成 11 條線段或射線，而每條線段又將平面的一部分一分為二，2條射線增加了一部分，因此 5個圓和1條直線最多可將平面分成 32個部分.【例6】 在一個西瓜上切6刀，最多能將瓜皮切成多少片？【解析】將西瓜看做一個球體，球體上任意一個切割面都是圓形，所以球

10、面上的切割線是封閉的圓周，考慮 每一次切割能增加多少瓜皮片.當(dāng)切1刀時，瓜皮被切成兩份，當(dāng)切第 2刀時，由于切割線相交，所以瓜皮被切成4分，切第n次時，新增加的切割線與原來的切割線最多有2(n1)個交點.這些交點將第n條切割線分成2 (n1)段，也就是說新增加的切割線使瓜皮數(shù)量增加了2(n_1),所以在西瓜上切6刀，最多能將瓜皮切成 1+1+2父1 +2M2+2父3 + 2父4+2父5 = 32片.【例7】 在一大塊面包上切 6刀最多能將面包切成多少塊.(注：面包是一個立體幾何圖形，切面可以是任何方向)【解析】題目相當(dāng)于6個平面能將空間劃分為多少個部分.通過找規(guī)律來尋找遞推關(guān)系，顯然的 1個平

11、面能將空間劃分成 2塊，2個平面能將空間劃分成 4塊, 3個平面能將空間劃分成 8個平面，當(dāng)增加到第四個平面時，第四個平面這能將原來空間中的8個部分中的其中幾個劃分.如圖：注意到第四個平面與其他三個平面相交形成3條直線，這三條直線將第四個平面分割成7個部分，而每一部分將原來三個平面劃分的8個空間中的7個劃分成兩份，所以 4個平面能將空間劃分成8+7 =15個部分.同樣的第五個平面與前四個平面分別相交成4條直線，這四條直線能將第5個平面分割成1 1 2 3 4 =1小部分，每一部分都劃分原空間中的某一區(qū)域，所以第五個平面能使空間中的區(qū) 域增加到15+11 =26個部分.當(dāng)增加到6個平面時，第六個

12、平面共被劃分成1+1+2+3+4+5 =16個部分，所以第6個平面能將空間中的區(qū)塊數(shù)增加到 26+16 = 42個部分.所以6刀能將面包切成 42塊.模塊二、整體法解決計數(shù)問題時，有時要“化整為零”，使問題變得簡單；有時反而要從整體上來考慮，從全局、從整體來研 究問題，反而有利于發(fā)現(xiàn)其中的數(shù)量關(guān)系.【例8（難度等級 ）一個正方形的內(nèi)部有1996個點，以正方形的 4個頂點和內(nèi)部的1996個點為頂點，將它剪成一些三角形.問：一共可以剪成多少個三角形？如果沿上述這些點中某兩點之間所連的線段剪開算作一刀，那么共需剪多少刀？【解析】方法一：歸納法如下圖，采用歸納法，列出 1個點、2個點、3個點一時可剪出

13、的三角形個數(shù)，需剪的刀數(shù).內(nèi)部I個點2個點3個點-9個點他個點三儡形個數(shù)468F i 20需典的刀數(shù)472®31L不難看出，當(dāng)正方形內(nèi)部有n個點時，可以剪成 2n+2個三角形，需剪 3n+l刀，現(xiàn)在內(nèi)部有1996個點，所以可以剪成 2M996+2=3994個三角形，需剪 3M996+1=5989刀.方法二：整體法.我們知道內(nèi)部一個點貢獻(xiàn) 360度角，原正方形的四個頂點共貢獻(xiàn)了 360度角，所以當(dāng)內(nèi)部有 n個點 時，共有360n+360度角，而每個三角形的內(nèi)角和為 180度角，所以可剪成（360n+360） T80=2n+2個 三角形.2n+2個三角形共有3X2n+2）=6n+6條邊，

14、但是其中有 4條是原有的正方形的邊，所以正方形內(nèi)部的 三角形邊有6n+64=6n+2條邊，又知道每條邊被 2個三角形共用，即每 2條邊是重合的，所以只用剪（6n+2） -2=3n+1 刀.本題中n=1996,所以可剪成 3994個三角形，需剪 5989刀.【鞏固】在三角形 ABC內(nèi)有100個點，以三角形的頂點和這 100點為頂點，可把三角形剖分成多少個小三角 形？【解析】整體法.100個點每個點周圍有360度，三角形本身內(nèi)角和為180度，所以可以分成 （360區(qū)100 +180廣180 =201個小三角形.【例9】 在一個六邊形紙片內(nèi)有 60個點，以這60個點和六變形的 6個頂點為頂點的三角形

15、，最多能剪出 個.【解析】設(shè)正六邊形內(nèi)有n個點，當(dāng)n=1時有6個三角形，每增加一個點，就增加2個三角形，n個點最多能剪出6+2（n+1）=2（n+2）個三角形.n=60時，可剪出124個三角形.注：設(shè)最多能剪出x個小三角形，則這些小三角形的內(nèi)角和為180"x.換一個角度看，匯聚到正六邊形六個頂點 處各角之和為 4M180",故這些 小三角形的內(nèi) 角總和為60M360口+4父180，于是 180rx = 60父 360 + 4 180解得 x =124.模塊三、對應(yīng)法將難以計數(shù)的數(shù)量與某種可計量的事物聯(lián)系起來，只要能建立一一對應(yīng)的關(guān)系，那么這兩種事物在數(shù)量上是相同的.事實上插

16、入法和插板法都是對應(yīng)法的一種表現(xiàn)形式.一、圖形中的對應(yīng)關(guān)系【例10】（難度等級 派）在8X8的方格棋盤中，取出一個由三個小方格組成的“噂（如圖），一共有多少種不同的方法？【解析】注意：數(shù) 不規(guī)則幾何圖形”的個數(shù)時，常用對應(yīng)法.第1步：找對應(yīng)圖形 每一種取法，有一個點與之對應(yīng)，這就是圖中的A點，它是棋盤上橫線與豎線的交點，且不在棋盤邊上.第2步：明確對應(yīng)關(guān)系從下圖可以看出，棋盤內(nèi)的每一個點對應(yīng)著4個不同的取法（“形的 角在2>2正方形的不同角”上）.第3步：計算對應(yīng)圖形個數(shù)由于在8>8的棋盤上，內(nèi)部有 7X7=49 （個）交叉點，第4步：按照對應(yīng)關(guān)系，給出答案故不同的取法共有49&g

17、t;4=196 （種）.評注:通過上面兩個范例我們知道 ，當(dāng)直接去求一個集合元素的個數(shù)較為困難的時候，可考慮采用相等的原則，把問題轉(zhuǎn)化成求另一個集合的元素個數(shù).【例11】（難度等級 派）在8>8的黑白相間染色的國際象棋棋盤中，以網(wǎng)格線為邊的、恰包含兩個白 色小方格與一個黑色小方格的長方形共有多少個？【解析】首先可以知道題中所講的1父3長方形中間的那個小主格為黑色，這是因為兩個白格不相鄰，所以不能在中間.顯然，位于棋盤角上的黑色方格不可能被包含在這樣的長方形中.下面分兩種情況來分析：第一種情況，一個位于棋盤內(nèi)部的黑色方格對應(yīng)著兩個這樣的1M 3長方形（一橫一豎）；第二種情況，位于邊上的黑色

18、方格只能對應(yīng)一個1黑3長方形.由于在棋盤上的32個黑色方格中，位于棋盤內(nèi)部的18個，位于邊上的有12個，位于角上的有2個， 所以共有18M2+12=48個這樣的長方形.本題也可以這樣來考慮：事實上，每一行都有6個1父3長方形，所以棋盤上橫、豎共有 1父3長方形6X8X2=96個.由于棋盤上的染色具有對稱性，因此包含兩個白色小方格與一個黑色小方格的長方形正好與包含兩個黑色小方格與一個白色小方格的長方形具有一一對應(yīng)關(guān)系，這說明它們各占一半，因此所求的長方形個數(shù)為 96+2 =48個.【鞏固】（難度等級 派）用一張如圖所示的紙片蓋住置方法？6 M6方格表中的四個小方格，共有多少種不同的放【解析】如圖

19、，將紙片中的一個特殊方格染為黑色，下面考慮此格在6父6方格表中的位置.易見它不能位于四個角上；若黑格位于方格表中間如圖淺色陰影所示的4父4正方形內(nèi)的某格時，紙片有 4種不同的放法，共計4x4x4=64種；若黑格位于方格表邊上如圖深色陰影所示的方格中時，紙片的位置隨之 確定，即只有1種放法，此類放法有 4x4=16種.所以，紙片共有64 +16 =80種不同的放置方法.【例12（難度等級 ”）圖中可數(shù)出的三角形的個數(shù)為 .【解析】這個圖不像我們以前數(shù)三角形那樣規(guī)則，粗看似乎看不出其中的規(guī)律，不妨我們?nèi)〕銎渲械囊粋€三 角形，發(fā)現(xiàn)它的三條邊必然落在這個圖形中的三條大線段上，而每三條大線段也正好能構(gòu)成

20、一個三 角形，因此三角形的個數(shù)和三條大線段的取法是一一對應(yīng)的關(guān)系，圖中一共有8條大線段，因此有C83 =56個三角形.【例13如圖所示，在直線 AB上有7個點，直線CD上有9個點.以AB上的點為一個端點、CD上的點為另一個端點的所有線段中，任意 的交點數(shù).3條線段都不相交于同一個點，求所有這些線段在AB與CD之間C【解析】常規(guī)的思路是這樣的：直線 AB上的7個點，每個點可以與直線 CD上的9個點連9根線段，然后再 分析這些線段相交的情況.如右圖所示，如果注意到下面這個事實：對于直線AB上的任意兩點 M、N與直線CD上的任意兩點P、Q都可以構(gòu)成一個四邊形 MNQP ,而這個四邊形的兩條對角線 M

21、Q、NP的交點恰好是我們 要計數(shù)的點，同時，對于任意四點 （AB與CD上任意兩點）都可以產(chǎn)生一個這樣的交點，所以圖中兩 條線段的交點與四邊形有一一對應(yīng)的關(guān)系.這說明，為了計數(shù)出有多少個交點，我們只需要求出在直線AB與CD中有多少個滿足條件的四邊形MNQP就可以了！從而把問題轉(zhuǎn)化為：在直線AB上有7個點，直線CD上有9個點.四邊形MNQP有多少個？其中點 M、N位于直線AB 上，點P、Q位于直線CD上.這是一個常規(guī)的組合計數(shù)問題，可以用乘法原理進(jìn)行計算：由于線段MN有C72=21種選擇方式，線2段PQ有C9 =36種選擇方式，根據(jù)乘法原理，共可產(chǎn)生21M36 =756個四邊形.因此在直線 AB與

22、CD 之間共有756個交點.、數(shù)字問題中的對應(yīng)關(guān)系【例14】有多少個四位數(shù)，滿足個位上的數(shù)字比千位數(shù)字大，千位數(shù)字比百位大， 百位數(shù)字比十位數(shù)字大？【解析】由于四位數(shù)的四個數(shù)位上的數(shù)的大小關(guān)系已經(jīng)非常明確，而對于從09中任意選取的4個數(shù)字，它們的大小關(guān)系也是明確的，那么由這4個數(shù)字只能組成1個符合條件的四位數(shù)（題目中要求千位比百位大，所以千位不能為 0,本身已符合四位數(shù)的首位不能為0的要求，所以進(jìn)行選擇時可以把0包含在內(nèi)），也就是說滿足條件的四位數(shù)的個數(shù)與從09中選取4個數(shù)字的選法是一一對應(yīng)的關(guān)系，那么滿足條件的四位數(shù)有 C140 =10父9父8父7 =210個. 4 3 2 1【鞏固】（難度

23、等級 派）三位數(shù)中，百位數(shù)比十位數(shù)大，十位數(shù)比個位數(shù)大的數(shù)有多少個？【解析】相當(dāng)于在10個數(shù)字中選出3個數(shù)字，然后按從大到小排列.共有10X9X8+ （3X2X 1） =120種.實 際上，前鋪中每一種劃法都對應(yīng)著一個數(shù).【例15】數(shù)3可以用4種方法表示為一個或幾個正整數(shù)的和，如 3, 1+2, 2+1, 1+1+1 .問：1999表示 為一個或幾個正整數(shù)的和的方法有多少種？【解析】我們將1999個1寫成一行，它們之間留有 1998個空隙，在這些空隙處，或者什么都不填，或者填 上“ 十 ”號.例如對于數(shù)3,上述4種和的表達(dá)方法對應(yīng)：1 1 1, 1+1 1, 1 1+1, 1十1十1.可見，將

24、1999表示成和的形式與填寫 1998個空隙處的方式之間是一一對應(yīng)的關(guān)系，而每一個空隙 處都有填“ 十 ”號和不填“ 十 ”號 2種可能，因此 1999可以表示為正整數(shù)之和的不同方法有 2 M2 研| 乂二2 1998種.1998個2相乘【例16】（2008年國際小學(xué)數(shù)學(xué)競賽）請問至少出現(xiàn)一個數(shù)碼3,并且是3的倍數(shù)的五位數(shù)共有多少個？【解析】五位數(shù)共有90000個，其中3的倍數(shù)有30000個.可以采用排除法，首先考慮有多少個五位數(shù)是3的倍數(shù)但不含有數(shù)碼 3. 首位數(shù)碼有8種選擇，第二、三、四位數(shù)碼都有9種選擇.當(dāng)前四位的數(shù)碼確定后，如果它們的和除以余數(shù)為0,則第五位數(shù)碼可以為 0、6、9;如果

25、余數(shù)為1,則第五位數(shù)碼可以為 2、5、8;如果 余數(shù)為2,則第五位數(shù)碼可以為 1、4、7.可見只要前四位數(shù)碼確定了，第五位數(shù)碼都有3種選擇，所以五位數(shù)中是 3的倍數(shù)但不含有數(shù)碼 3的數(shù)共有8M9乂9父9黑3=17496個. 所以滿足條件的五位數(shù)共有 30000 -17496 =12504個.三、對應(yīng)與階梯型標(biāo)數(shù)法【例17】游樂園的門票1元1張，每人限購1張.現(xiàn)在有10個小朋友排隊購票，其中 5個小朋友只有1元 的鈔票，另外5個小朋友只有2元的鈔票，售票員沒有準(zhǔn)備零錢.問有多少種排隊方法，使售票 員總能找得開零錢？【解析】與類似題目找對應(yīng)關(guān)系.要保證售票員總能找得開零錢，必須保證每一位拿2元錢的

26、小朋友前面的若干小朋友中，拿1元的要比拿2元的人數(shù)多，先將拿 1元錢的小朋友看成是相同的，將拿2元錢的小朋友看成是相同的，可以利用斜直角三角模型.在下圖中，每條小橫線段代表1元錢的小朋友，每條小豎線段代表 2元錢的小朋友，因為從 A點沿格線走到B點，每次只能向右或向上走，無論到途中哪一點，只要不超 過斜線，那么經(jīng)過的小橫線段都不少于小豎線段，所以本題相當(dāng)于求下圖中從A到B有多少種不同走法.使用標(biāo)數(shù)法，可求出從 A到B有42種走法.但是由于10個小朋友互不相同，必須將他們排隊，可以分成兩步，第一步排拿2元的小朋友，5個人共有5! =120種排法；第二步排拿到1元的小朋友，也有120種排法，所以共

27、有3父3 =14400種排 隊方法.這樣，使售票員能找得開零錢的排隊方法共有42x14400=604800（種）.【例18【解析】（ 2008年第一屆“學(xué)而思杯”五年級試題）學(xué)學(xué)和思思一起洗5個互不相同的碗，思思洗好的碗一個一個往上摞，學(xué)學(xué)再從最上面一個一個地拿走放入碗柜摞成一摞，思思一邊洗，學(xué)學(xué)一邊拿， 那么學(xué)學(xué)摞好的碗一共有種不同的摞法.我們把學(xué)學(xué)洗的 5個碗過程看成從起點向右走5步（即洗幾個碗就代表向右走幾步），思思拿5個碗的過程看成是向上走5步（即拿幾個碗就代表向上走幾步），摞好碗的摞法，就代表向右、向上走5步到達(dá)終點最短路線的方法.由于洗的碗要多余拿的碗，所以向右走的路線要多余向上走

28、的路線，所以我們用下面的斜三角形進(jìn)行標(biāo)數(shù)，共有42種走法，即代表 42種摞法.【例19【解析】（第七屆走美試題）一個正在行進(jìn)的 8人隊列，每人身高各不相同，按從低到高的次序排列，現(xiàn)在他們要變成并列的 2列縱隊，每列仍然是按從低到高的次序排列，同時要求并排的每兩人中左邊的人比右邊的人要矮，那么，2列縱隊有 種不同排法.首先，將8人的身高從低到高依次編號為 1、2、3、4、5、6、7、8,現(xiàn)在就相當(dāng)于要將這 8個數(shù)填到一個4M 2 的方格中，要求每一行的數(shù)依次增大，每一列上面的要比下面的大.下面我們將1、2、3、4、5、6、7、8依次往方格中填，按照題目規(guī)則，很容易就發(fā)現(xiàn)：第二行填的的數(shù)字的 個數(shù)

29、永遠(yuǎn)都小于或等于第一行數(shù)字填的個數(shù).也就是說，不能出現(xiàn)下圖這樣的情況.而這個正好是“階梯型標(biāo)數(shù)”12345在這個階梯型方格中，橫格代表在第一行的四列，縱格代表第二行的四列，那么此題所有標(biāo)數(shù)的方法就相當(dāng)于從 A走到B的最短路線有多少條. 例如，我們選擇一條路線：14 B【鞏固】將112這12個數(shù)填入到2行6列的方格表中，使得每行右邊比左邊的大，每一列上面比下面的大,共有多少種填法？【解析】根據(jù)對應(yīng)關(guān)系，再運用階梯型標(biāo)數(shù)法畫圖如下：共有132種填法.四、不完全對應(yīng)關(guān)系【例20圓周上有12個點，其中一個點涂紅，還有一個點涂了藍(lán)色，其余10個點沒有涂色，以這些點為頂點的凸多邊形中，其頂點包含了紅點及藍(lán)

30、點的多邊形稱為雙色多邊形；只包含紅點（藍(lán)點）的多邊形稱為紅色（藍(lán)色）多邊形.不包含紅點及藍(lán)點的稱無色多邊形.試問，以這12個點為頂點的所有凸多邊形（邊數(shù)可以從三角形到 12邊形）中，雙色多邊形的個數(shù)與無色多邊形的個數(shù)，哪一種較 多？多多少個？【解析】從任意一個雙色的 N邊形出發(fā)（N之5時），在去掉這個雙色多邊形中的紅色頂點與藍(lán)色頂點后，將 得到一個無色的 N -2邊形；另一方面，對于一個任意的無色的M邊形，如果加上紅色頂點和藍(lán)色頂點，就得到一個雙色的 M +2邊形，所以無色多邊形與雙色多邊形中的五邊形以上的圖形是一一 對應(yīng)的關(guān)系，所以雙色多邊形的個數(shù)比較多，多的是雙色三角形和雙色四邊形的個數(shù).

31、而雙色三角 形有10個，雙色四邊形有 G2）=45個，所以雙色多邊形比無色多邊形多10 + 45=55個.【例21】有一類各位數(shù)字各不相同的五位數(shù)M ,它的千位數(shù)字比左右兩個數(shù)字大，十位數(shù)字也比左右兩位數(shù)字大.另有一類各位數(shù)字各不相同的五位數(shù)W ,它的千位數(shù)字比左右兩個數(shù)字小，十位數(shù)字也比左右兩位數(shù)字小.請問符合要求的數(shù)M與W,哪一類的個數(shù)多？多多少？【解析】M與W都是五位數(shù)，都有千位和十位與其它數(shù)位的大小關(guān)系，所以兩類數(shù)有一定的對應(yīng)關(guān)系.比如有一個符合要求的五位數(shù)M =ABCDE （A不為0）,那么就有一個與之相反并對應(yīng)的五位數(shù)（9 A）（9 B）（9 C）（9 D）（9 E）必屬于 W類,

32、比如13254為M類，則與之對應(yīng)的 86754為W類. 所以對于M類的每一個數(shù)， W類都有一個數(shù)與之對應(yīng).但是兩類數(shù)的個數(shù)不是一樣多，因為 M類 中0不能做首位，而 W類中9可以做首位.所以 W類的數(shù)比M類的數(shù)要多，多的就是就是首位為9的符合要求的數(shù).計算首位為9的W類的數(shù)的個數(shù)，首先要確定另外四個數(shù)， 因為要求各不相同，從除9外的其它9個 數(shù)字中選出4個，有C4 =126種選法.對于每一種選法選出來的4個數(shù)，假設(shè)其大小關(guān)系為 A4AA3AA2 > A,由于其中最小的數(shù)只能在千位和十位上，最大的數(shù)只能在百位和個位上，所以符合要求的數(shù)有2類：千位、十位排 A、A2,有兩種方法，百位、十位排

33、A3、A4,也有兩種方法，故此時共有4種；千位、十位排 A、A3,只能是千位A3,百位A4,十位A,個位A2,只有1種方法.根據(jù)乘法原理，首位為 9的W類的數(shù)有126乂（4+1 ）=630個.故W類的數(shù)比M類的數(shù)多630個.【例22 用1元，2元，5元，10元四種面值的紙幣若干張（不一定要求每種都有）,組成99元有P種方法， 組成101元有Q種方法，則Q -P =.【解析】由于101-99=2,所以對于組成99元的每一種方法，只要再加上一張2元的，即可組成101元；而對于組成101元的方法，如果其中包含有一張2元的，那么去掉這張 2元的，即可得到一種組成 99元的方法.可見組成99元的方法與組

34、成101元的某些方法之間存在對應(yīng)的關(guān)系，組成101元的所有方法中，除去這些與組成99元的方法對應(yīng)的方法，剩下的都是不包含有 2元紙幣的組成方法.所 以Q比P多的就是用1元，5元，10元這三種面值的紙幣組成 101元的方法的總數(shù).假設(shè)用x張1元的，y張5元的，z張10元的可以組成101元，則x + 5y+10z = 101 .由于10zE101,所以z<10 .即10元的可以有010張.如果10元的張數(shù)確定了， 那么有x+5y=10110z=10（10z）+1=5（202z）+1 ,那么y的值可以為 0至1J（202z）,也就是對每一個 z的值，y都可以有202z+1=212z種可能，相應(yīng)

35、地5元紙幣的 張數(shù)也有21-2z種取法.而當(dāng)10元和5元的張數(shù)都確定了以后，1元紙幣的張數(shù)也就確定了，這樣也就確定了組成101元的方法.所以只需要看取 10元和5元的共有多少種取法.如果10元的取0張，即z = 0 ,則21 -2z=21 ,即5元的有21種取法； 如果10元的取1張，即z=1 ,則212z=19 ,即5元的有19種取法； 如果10元的取2張，即z=2 ,則21 -2z=17 ,即5元的有17種取法；如果10元的取10張，即z=10,則212z=1,即5元的有1種取法;所以總數(shù)為 21+19+17+川+1=112=121.那么 Q _P =121 .模塊四、遞推法對于某些難以發(fā)

36、現(xiàn)其一般情形的計數(shù)問題，可以找出其相鄰數(shù)之間的遞歸關(guān)系，有了這一遞歸關(guān)系就可以利 用前面的數(shù)求出后面未知的數(shù)，這種方法稱為遞推法.【例23（難度等級 ）有一堆火柴共 12根，如果規(guī)定每次取 13根，那么取完這堆火柴共有多少 種不同取法？【解析】取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種 數(shù)等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完這堆火柴一共有 927種方法.【鞏固】 （難度等級 派）一堆蘋果共有 8個，如果規(guī)定每次取 13個，

37、那么取完這堆蘋果共有多少種 不同取法？【解析】取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以后取任意個蘋果的種 數(shù)等于取到前三個蘋果所有情況之和，以此類推，參照上題列表如下：1個2個3個4個5個6個7個8個124713244481取完這堆蘋果一共有 81種方法.【例24】有10枚棋子，每次拿出 2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？【解析】本題可以采用遞推法，也可以進(jìn)行分類討論，當(dāng)然也可以直接進(jìn)行枚舉.（法1）遞推法.假設(shè)有n枚棋子，每次拿出2枚或3枚，將n枚棋子全部拿完的拿法總數(shù)為 小種.貝 U a? =1 , a3 =1 ,=1 .由于每次拿出2

38、枚或3枚，所以an =an+an/（ n之5）.所以，a5 a2 "*"a3 2 j a6=a3+a4=2； a7=a4+a5=3； a8=a5+a6=4； a9 - a6 "*"a7 - 5 j a10 =a7 +a8 =7 .即當(dāng)有10枚棋子時，共有7種不同的拿法.（法2）分類討論.由于棋子總數(shù)為10枚，是個偶數(shù)，而每次拿 2枚或3枚，所以其中拿3枚的次數(shù)也應(yīng)該是偶數(shù).由 于拿3枚的次數(shù)不超過3次，所以只能為0次或2次.若為0次，則相當(dāng)于2枚拿了 5次，此時有1種拿法；若為2次，則2枚也拿了 2次，共拿了 4次，所以此時有C：=6種拿法.根據(jù)加法原理

39、，共有1+6=7種不同的拿法.【例25（難度等級 派）用1M3的小長方形覆蓋3M8的方格網(wǎng)，共有多少種不同的蓋法？【解析】如果用1父3的長方形蓋3。的長方形，設(shè)種數(shù)為 小，則a1=1, a2=1,%=2,對于n24,左邊可能豎放1個1父3的，也可能橫放 3個1父3的，前者有an-1種，后者有an-3種，所以an=an-1+an-3,依照 這條遞推公式列表：3父13M23M33M43M53M63M73M8112346913所以用1 m3的小長方形形覆蓋 3父8的方格網(wǎng)，共有13種不同的蓋法.【例26（難度等級 派）如下圖，一只蜜蜂從 A處出發(fā)，回到家里 B處，每次只能從一個蜂房爬向右 側(cè)鄰近的蜂

40、房而不準(zhǔn)逆行，共有多少種回家的方法？【解析】按照蜜蜂只能從小號碼的蜂房爬近相鄰大號碼的蜂房的原則，運用標(biāo)號法進(jìn)行計算.如右圖所示,小蜜蜂從A出發(fā)到B處共有296種不同的回家方法.【例27】有20個石子，一個人分若干次取，每次可以取1個，2個或3個，但是每次取完之后不能留下質(zhì)數(shù)個，有多少種方法取完石子？（石子之間不作區(qū)分，只考慮石子個數(shù)）【解析】如果沒有剩下的不能使質(zhì)數(shù)這個條件，那么遞推方法與前面學(xué)過的遞推法相似，只不過每次都是前面3個數(shù)相加.現(xiàn)在剩下的不能是質(zhì)數(shù)個，可以看作是質(zhì)數(shù)個的取法總數(shù)都是0,然后再進(jìn)行遞推.剩 下 的 石 子 數(shù)20191817161514131211109876543

41、210取101012305051015025025002525法總 數(shù)【鞏固】有20個相同的棋子，一個人分若干次取，每次可取1個，2個，3個或4個，但要求每次取之后留下的棋子數(shù)不是 3或4的倍數(shù)，有 種不同的方法取完這堆棋子 .【解析】把20、0和20以內(nèi)不是3或4的倍數(shù)的數(shù)寫成一串，用遞推法把所有的方法數(shù)寫出來：2019171413111075210112246121818183654【例28】4個人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方法？【解析】設(shè)第n次傳球后，球又回到甲手中的傳球方法有an

42、種.可以想象前n-1次傳球，如果每一次傳球都任選其他三人中的一人進(jìn)行傳球，即每次傳球都有3種可能，由乘法原理，共有3M3M3-、.3 = 3力種）（n 1）個 3傳球方法.這些傳球方法并不是都符合要求的，它們可以分為兩類，一類是第n-1次恰好傳到甲手中，這有an二種傳法，它們不符合要求，因為這樣第n次無法再把球傳給甲； 另一類是第n-1次傳球，球不在甲手中，第n次持球人再將球傳給甲，有an種傳法.根據(jù)加法原理，有Wn+an三3M3M'Q =3（n 1）個 3由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方法是不存在的，所以a=0 .利 用遞推 關(guān)系可 以得到：a2=30=3 , a3

43、=3x3-3=6 , a4 =3x3x3-6 =21 a5 =3x3x3x3-21 =60 .這說明經(jīng)過5次傳球后，球仍回到甲手中的傳球方法有60種.本題也可以列表求解.由于第n次傳球后，球不在甲手中的傳球方法，第n+1次傳球后球就可能回到甲手中，所以只需求出第四次傳球后，球不在甲手中的傳法共有多少種.第n次傳球傳球的方法球在甲手中的傳球方法球小在甲手中的傳球方法130329363276214812160524360183從表中可以看出經(jīng)過五次傳球后，球仍回到甲手中的傳球方法共有60種.【鞏固】五個人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過4次傳球后，球仍回到甲手中.問：共有多少種傳球方

44、式？【解析】遞推法.設(shè)第n次傳球后球傳到甲的手中的方法有an種.由于每次傳球有 4種選擇，傳n次有4n次可能.其中有的球在甲的手中， 有的球不在甲的手中，球在甲的手中的有an種，球不在甲的手中的，下一次傳球都可以將球傳到甲的手中，故有an出種.所以an +an書=4n .由于ai =0 ,所以a2 =41 -ai =4 , a3 =42 -a? =12 , a4=43 -a? =52 .即經(jīng)過4次傳球后，球仍回 到甲手中的傳球方法有 52種.【例29】（2009年清華附中考題）設(shè)八、E為正八邊形 ABCDEFGH的相對頂點，頂點 A處有一只青蛙，除 頂點E外青蛙可以從正八邊形的任一頂點跳到其相

45、鄰兩個頂點中任意一個，落到頂點E時青蛙就停止跳動，則青蛙從頂點 A出發(fā)恰好跳10次后落到E的方法總數(shù)為 種.【解析】可以使用遞推法.回到A跳到B或H跳到C或G跳到D或FW E1步12步213步314步6425步1046步201487步34148步6848289步11648其中，A列的每個數(shù)都等于它的上一行的第二列的數(shù)的2倍，第二列的每一個數(shù)都等于它的上一行的第一列和第三列的兩個數(shù)的和，第三列的每一個數(shù)都等于它的上一行的第二列和第四列的兩 個數(shù)的和，第四列的每一個數(shù)都等于它的上一行的第三列的數(shù)，第五列的每一個數(shù)都等于都等于它 的上一行的第四列的數(shù)的 2倍.這一規(guī)律很容易根據(jù)青蛙的跳動規(guī)則分析得來.所以，青蛙第10步跳到E有48M 2 =96種方法.【鞏固】在正五邊形 ABCDE上，一只青蛙從 A點開始跳動，它每次可以隨意跳到相鄰兩個頂點中的一個上, 一旦跳到D點上就停止跳動.青蛙在 6次之內(nèi)（含6次）跳到D點有 種不同跳法.【解析】采用遞推的方法.列表如下:跳到A跳到B跳到CW D跳到E1步112步2113步3124步5325步8356步1385其中，根據(jù)規(guī)則，每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到D點上就停止跳動.所以，每一步跳到 A的跳法數(shù)等于上一步跳到