第9講 計(jì)數(shù)綜合之歸納遞推映射計(jì)數(shù)一

第九講計(jì)數(shù)綜合之歸納遞推映射計(jì)數(shù)一模塊一、斐波那契數(shù)列的應(yīng)用例1．一堆蘋果共有8個，如果規(guī)定每次取1~2個，那么取完這堆蘋果共有34種不同的取法。解：取1個有1種取法；取2個有2種取法；取3個有1+2=3種取法，即在取1個的基礎(chǔ)上再取2個或在取了兩個的基礎(chǔ)上再取1個；于是取4個有2+3=5種取法；于是a1=1，a2=2，a3=1+2=3，a4=2+3=5，a5=3+5=8，a6=5+8=13，a7=8+13=21，a8=13+21=34.所以取完這對蘋果有34種不同的取法。模塊二、標(biāo)數(shù)法例2．“五一”長假就要到了，小新和爸爸決定去黃山玩，聰明的小朋友請你找找看，從北京到黃山的最短路線共有10條。解：所以一共有10條路線。例3．一只蜜蜂從A處出發(fā)，回到家里B處，每次只能從一個蜂房爬向右側(cè)臨近的蜂房，而不準(zhǔn)逆行，共有種回家的方法。解：所以一共有55+34=89種回家的方法。模塊三、平面分割問題例4．在一個平面上畫8個圓，最多可以把平面分成58個部分。解：一個圓把平面分成2部分，第2個圓與第一個圓有兩個交點(diǎn)，這兩個交點(diǎn)把圓分成兩段弧，每段弧都分出一塊平面區(qū)域，于是兩個圓分成4個部分；以此類推，第三個圓與前兩個圓有四個交點(diǎn)，分成四段弧，多出4個區(qū)域，4+4=8；……得2+2+4+6+8+10+12+14=58.模塊四、圖形染色問題例5．如圖所示，一個圓環(huán)被分成8部分，現(xiàn)將每一部分染上紅、黃、藍(lán)三種顏色之一，要求相鄰的兩部分顏色不同，共有258種染色方法。解：在第一處選一種顏色涂色（例如紅色），有3種選法，在它的旁邊一塊涂色有2種方法（圖黃色或藍(lán)色），接著再涂色，可以看做是傳球的方式，以紅色為例，傳球7次，不傳回自己手中，而在第8次恰好傳回到自己手中。列表表示：次數(shù)紅黃藍(lán)01001011221132334655510111162221217424343886所以應(yīng)該有3×86=258種方法，解2：設(shè)圓環(huán)被分成n部分，共有An種染色方法，除了第一部分有3種染法，其余各部分都有兩種染法，但這里包括最后一部分和第一部分顏色相同的情況，恰是An?1，因此An=3×2n?1?An?1，由A1=3，A2=6，得A3=3×22?A2=6，A4=3×23?A3=18，A5=3×24?A4=30，A6=3×25?A5=66，A7=3×26?A6=126，A8=3×27?A7=258.模塊五、數(shù)字排列問題例6．用1~9這9個數(shù)字組成一個沒有重復(fù)數(shù)字的九位數(shù)，滿足以下條件：每一位上的數(shù)字要么大于它前面的所有數(shù)字，要么小于它前面的所有數(shù)字，請問：這樣的九位數(shù)有256個。解：只有1個數(shù)字1排列，有1種方法，a1=1；兩個數(shù)字1，2排列有12，21都可以，有2種方法，a2=2；三個數(shù)字1、2、3排列，有123、321、231、213．有4種排法，a3=1+a1+a2=4；四個數(shù)字1、2、3、4排列，有4321、3421、2341、3241、1234、3214、2314、2134，有8種排法；……an=1+a1+a2+……+an?1，an?1=1+a1+a2+……+an?2，兩式相減得an?an?1=an?1，所以an=2an?1，9個數(shù)是a9=28×a1，8個2相乘，即28=256種．答：這樣的九位數(shù)共有256個。解2：只有1個數(shù)字1排列，有1種方法，a1=1；兩個數(shù)字1，2排列有12，21都可以，有2種方法，a2=2；對于9個數(shù)字的問題，考慮個位數(shù)字，若個位數(shù)字為9，那么它前面的8個數(shù)字能排出a8種形式；若個位數(shù)字為1，前面的8個數(shù)字（2、3、4、……、9）也有a8種排法，若個位數(shù)字不是1或9，那么這種排法一定是錯誤的，（因?yàn)樗那懊嬗?和9，它不可能大于前面所有的數(shù)字，也不會小于前面所有的數(shù)字）；所以a9=2×a8=22×a7=23×a6=……=28×a1=28=256。模塊六、經(jīng)典歸納遞推計(jì)數(shù)問題例7．甲、乙、丙三名同學(xué)練習(xí)傳球，每人都可以把球傳給另外兩個人中的任意一個，從甲開始，經(jīng)過6次傳球后球仍然回到了甲的手中，請問：整個傳球過程共有22種不同的可能。解：采用“傳球法”，甲拿著球，所以最開始甲標(biāo)1，乙、丙都標(biāo)0；接著甲必須由乙、丙傳球給他，所以他下方的數(shù)必須由乙、丙累加給他；其余兩人同理。根據(jù)這樣的規(guī)則，我們列表得到如下的結(jié)果：甲乙丙0100101122113233465551011116222121所以第6次傳回甲有22種不同的方法。例8．圓周上共有15個點(diǎn)，A1，A2，……，A15，以這些點(diǎn)為頂點(diǎn)連出5個三角形，要求任何兩個三角形沒有公共點(diǎn)，共有91種連結(jié)方法。解：（1）如果圓上只有3個點(diǎn)，那么只有一種連法；

（2）如果圓上有6個點(diǎn)，除A1所在三角形的三頂點(diǎn)外，剩下的三個點(diǎn)一定只能在A1所在三角形的一條邊所對應(yīng)的圓弧上，表1給出這時有可能的連法有3種．（3）如果圓上有9個點(diǎn)，考慮A1所在的三角形．此時，其余的6個點(diǎn)可能分布在：①A1所在三角形的一個邊所對的弧上；②也可能三個點(diǎn)在一個邊所對應(yīng)的弧上，另三個點(diǎn)在另一邊所對的弧上；在表2中用“+”號表示它們分布在不同的邊所對的弧；如果是情形①，則由（2），這六個點(diǎn)有三種連法；如果是情形②，則由①，每三個點(diǎn)都只能有一種連法；共有12種連法．（4）考慮圓周上有12個點(diǎn)．同樣考慮A1所在三角形，剩下9個點(diǎn)的分布有三種可能：①9個點(diǎn)都在同一段弧上；

②有6個點(diǎn)是在一段弧上，另三點(diǎn)在另一段弧上；③每三個點(diǎn)在A1所在三角形的一條邊對應(yīng)的弧上．得到表3；共有12×3+3×6+1=55種．（5）最后考慮圓周上有15個點(diǎn)．同樣考慮A1所在三角形，剩下12個點(diǎn)的分布有三種可能：①12個點(diǎn)都在同一段弧上；②有9個點(diǎn)是在一段弧上，另3點(diǎn)在另一段弧上；③有6個點(diǎn)在A1所在三角形的一條邊對應(yīng)的弧上．另外6個點(diǎn)在另一條圓弧上；④分別有3個點(diǎn)在A1所在三角形的三邊對應(yīng)的弧上。得到表4；共有55×3+12×6+9×3+3×3=273種．A1所在的三角形余下的點(diǎn)種數(shù)A1A2A31255A1A2A151255A1A15A141255A1A2A63+912A1A2A133+912A1A15A53+912A1A15A113+912A1A5A63+912A1A12A113+912A1A2A96+63×3A1A15A86+63×3A1A8A96+63×3A1A5A93+3+63A1A5A123+3+63A1A7A123+6+33解2：設(shè)有n個點(diǎn)共有fn種連結(jié)方式，1．顯然f3=1；2．若有六個點(diǎn)，可以選三個相鄰的點(diǎn)，不妨從A1開始，包含A1的兩個相鄰的點(diǎn)的選法有3種，那么剩下三個點(diǎn)就有f3種連結(jié)方式，所以共有f6=3f3=3，3．若有九個點(diǎn)，(1)可以選三個相鄰的點(diǎn)，那么剩下六個點(diǎn)就有f6種連結(jié)方式，不妨從A1開始，包含A1的三個相鄰的點(diǎn)的選法有三種，所以共有3f6=9；(2)可以選三個點(diǎn)連接成三角形后，三角形兩邊各有三個點(diǎn)，不妨從A1開始，包含A1的三個點(diǎn)的選法有三種，那么剩下六個點(diǎn)就有3f3種連結(jié)方式，所以共有3f3×f3=3，因此f9=9+3=12；4．若有12個點(diǎn)，同理有f12=3f9+6f6f3+f3f3f3=3×12+6×3+1=55；5．若有15個點(diǎn)，同理有f15=3f12+6f3f9+3f6f6+3f6f3f3=273因此共有273種連結(jié)方式.隨堂練習(xí)1．一個樓梯共有12級階梯，規(guī)定每步可以邁1級、2級或3級臺階，走完這12級臺階，一共有927種不同的走法。解：邁1級，方法有1種；邁2級，方法有1+1，2，共2種；邁3級，有1+1+1，1+2，2+1，3共4種；即a1=1，a2=2，a3=4，以后的每一項(xiàng)是它前面三項(xiàng)的和，所以a4=7，a5=13，a6=24，a7=44，a8=81，a9=149，a10=274，a11=504，a12=927。2．下圖為某城市的街道示意圖，C處正在挖下水道，不能通車，從A到B處的最短路線共有431條。解：共有431條路線。3．按箭頭所指的方向行走，從A到I共有29條不同的路線。解：共有29條路線。4．一個矩形把平面分成兩部分，那么8個矩形最多把平面分成226部分。解：一個長方形可分內(nèi)外兩部分，第2個長方形有四條邊，每條邊都可以掛一下原長方形的每個角，這樣就產(chǎn)生8個交點(diǎn)，這8個交點(diǎn)自然把第2個長方形這樣一個封閉圖形分成8段（有直有彎），每段穿過一個部分一分為2，新增8個，所以2+8=10，第3個長方形的每條邊現(xiàn)在可以掛到原有2個長方形的8個角，最多可產(chǎn)生16個交點(diǎn)，同理這16個交點(diǎn)把第三個長方形本身分成16段，每段穿過一個部分，又新增加16個，共2+8+16=26個。依次類推得到n個矩形得到的平面區(qū)域是2+2×4+2×2×4+2×3×4+……+2×(n?1)×4=2+2×[1+2+3+……+(n?1)]×4=2+2××4=2+4n(n?1).所以8個矩形得到2+4×8×7=226個部分。5．如圖所示，一個圓被分成5部分，現(xiàn)將每一部分染上紅、黃、藍(lán)、綠四種顏色之一，要求相鄰的兩部分顏色不同，則共有240種不同的染色方法。解1：現(xiàn)將五個部分命名為A、B、C、D、E，選定A先染色，則A有4種顏色可選（例如選紅色）；再看B可以有3種顏色可選（例如選黃色），則C可選“紅、藍(lán)、綠”，E可選“黃、藍(lán)、綠”，在C、E的選項(xiàng)中如果都選藍(lán)或都選綠，則D有3種選法；如果C、E選不同的顏色（如C選紅、E選藍(lán)，這樣的搭配有7種方法），則D有2種選法；于是總數(shù)是4×3×(2×3+7×2)=240（種）方法。解2：設(shè)圓被分成n部分，共有An種染色方法，除了第一部分有4種染法，其余各部分都有3種染法，但這里包括最后一部分和第一部分顏色相同的情況，恰是An?1，因此An=4×3n?1?An?1，如果只有一個部分，有4種方法；如果有2個部分有4×3=12種方法；如果有3個部分，有4×32?12=24種方法；如果有4個部分，有4×33?24=84種方法；現(xiàn)在有5個部分，一共與4×34?84=240種方法。解3：用傳球的方法，對于A，有4種方法，假定A涂紅色，則經(jīng)過4次傳球，最后傳到E，而此時E的顏色不是紅色即可。次數(shù)紅黃藍(lán)綠010001011123222367774202020所以不是紅色的情況有20+20+20=60種，最后結(jié)果是4×60=240（種）不同的涂色方法。6．用2、4、6三個數(shù)字來構(gòu)造六位數(shù)，但是不允許有兩個連著的2出現(xiàn)在六位數(shù)中（例如626442是允許的，226426就不允許），問這樣的六位數(shù)共有448個。解：如果沒有限制，用2、4、6構(gòu)造六位數(shù)，可以有3×3×3×3×3×3=36=729，其中6個都是2的有1個；有5個2的共有6×2=12個；有4個2的共有個；有3個2且3個2連在一起有4×2×2×2=32個，若3個2中恰好有2個2連在一起，則有個，若恰好有2個2，且這2個2連在一起，則有個，這樣符合條件是六位數(shù)有729?(1+12+60+32+96+80)=448個。解2：如果沒有2，6個數(shù)字都由4、6組成，有2×2×2×2×2×2=26=64（個）；如果恰好有1個2，先把2放好，有6種方法，其余位置放4或6，一共有6×25=192種方法；如果恰好有2個2，且它們不相鄰，有種方法，其余位置放4或6，有×24=160種方法；如果恰好有3個2，且它們都不相鄰，有種方法，其余位置放4或6，有×23=32種方法；所以一共有64+192+160+32=448解3：用傳球的思路，即2的后面不是2，4、6的后面可以任意填；位置246111122333688416222254460606120164164合計(jì)448

7．四個人分別穿著紅、黃、綠、藍(lán)四種顏色的球衣練習(xí)傳球，每個人都可以把球傳給另外三個人中的任意一個，先由紅衣人發(fā)球，并作為第一次傳球，經(jīng)過8次傳球仍然回到紅衣人手中，請問：整個傳球過程共有種不同的可能。解：采用“傳球法”，穿紅球衣的拿著球，所以最開始把他標(biāo)為1，其他人都標(biāo)為0；根據(jù)，我們列表得到如下的結(jié)果：紅黃綠藍(lán)010001011123222367774212020205606161616183182182182754654754754781641164016401640所以第8次傳回穿紅球衣有1641種不同的方法。8．圓周上共有10個點(diǎn)，A1，A2，……，A10，以這些點(diǎn)為頂點(diǎn)連出5條線段，要求任何兩條線段之間都沒有公共點(diǎn)，共有種連結(jié)方法。解：（1）如果圓上只有2個點(diǎn)，那么只有一種連法；（2）如果圓上有4個點(diǎn)，除A1所在線段的兩個頂點(diǎn)外，剩下的兩個點(diǎn)一定只能在A1所在線段的一邊所對應(yīng)的圓弧上，這時有可能的連法有2種．（3）如果圓上有6個點(diǎn)，A1所在的線段余下的點(diǎn)種數(shù)A1A242A1A642A1A42+21共有的連線方法為5種；（4）如果圓上有8個點(diǎn)，A1所在的線段余下的點(diǎn)種數(shù)A1A265A1A865A1A42+42A1A64+22共有的連線方法為14種；（5）如果圓上有10個點(diǎn)，A1所在的線段余下的點(diǎn)種數(shù)A1A2814A1A10814A1A42+65A1A86+25A1A64+42×2所以一共有14×2+5×2+4=42（種）方法。解2：設(shè)有n個點(diǎn)共有fn種連結(jié)方式，1．顯然f2=1；2．若有四個點(diǎn)，可以選兩個相鄰的點(diǎn)，不妨從A1開始，包含A1