1、組合計數問題的基本方法遞推(學生版 )一、基礎問題呈現1.欲登上第10級臺階 ,若每步只能跨上一級或兩級, 則不同上臺階的方法數為【】 .A.144B.122C.89D.552.五個人排成一列, 重新站隊時 , 若各人都不站在原來的位置上, 則不同站隊的方法數為【】 .A.60B.44C.36D.243. 若用四種不同顏色給四邊形的四 n 個頂點染色 , 每點染一種顏色 , 相鄰的頂點染不同的顏色 , 則不同的染色方法數為【】 .A.84B.72C.48D.244. 甲、乙、丙、丁四人相互傳球, 第一次甲傳給乙、丙、丁中的任一人, 第二次由拿球者再傳給其他人中任一人 , 這樣共傳了四次 , 則

2、第四次球恰傳回到甲的方法數為【】 .A.42B.27C.24D.215. 甲、乙二人拿兩顆骰子做拋擲游戲 , 規則如下 : 若擲出的點數之和為 3 的倍數時 , 原擲骰子的人再繼續擲；若擲出的點數不是3 的倍數時就由對方接著擲. 若第一次由甲開始擲, 則第六次恰由甲擲的概率為【】.365364C.122121A.B.243D.729729243二、推廣問題解決6. 欲登上第 n 級樓梯 , 如果每步只能跨上一級或兩級, 求不同的方法數 .7. 已知 n 個人排成一列 , 重新站隊時 , 各人都不站在原來的位置上 , 求不同的方法數 .8. 用 m (m3) 種不同顏色給n ( n3) 邊形 A

3、1 A2An 的 n 個頂點染色 , 每點染一種顏色, 相鄰的頂點染不同的顏色 , 求不同的染色方法數.9. 有 m(m N * ) 個人相互進行 n(nN * ) 次傳球 , 由甲先傳 , 第一次甲傳給其他 m 1 個人中的任一人 , 第二次由拿球者再傳給其他人中任一人, 求這樣經過 n 次傳球 , 球回到甲手中的傳球方法數 .10. 甲、乙二人拿兩顆骰子做拋擲游戲 , 規則如下 : 若擲出的點數之和為 3的倍數時 , 原擲骰子的人再繼續擲 .若擲出的點數不是3 的倍數時就由對方接著擲, 第一次由甲開始擲, 求第 n 次仍由甲擲的概率Pn .第1頁共8頁三、能力問題測評ED11. 如圖 ,

4、將 A, B, C , D , E, F 這六個區域著四種不同的顏色, 每個區域著一種顏色, 且相AFC鄰區域著不同的顏色, 不同著色方法數為_.B12.由 0 和 1組成的長度為 n 的排列中 , 沒有兩個 1相連的排列個數記為 an ( 例如 , 排列 00101,10010的長度均為 5 ), 則 a8 _.13.現有甲、 乙兩人輪流擲一枚質地均勻的正方體骰子, 規定 : 如果某人某一次擲出 1點 , 那么下一次就繼續由此人擲；如果某人擲出的是其他的點數, 那么就由另一個人來擲. 若第一次由甲擲, 則第 n 次仍由甲擲的概率為 _.14. 從集合 A 1,2,3,4 中任取五個數 ( 可

5、重復 ) 排成一個五位數 , 要求首位只能排 1, 且任意相鄰兩位置不能排同一數 , 則末位恰也是1的五位數的個數為_.15. 若設集合 A 1,2, ,10 , 則滿足 “每個子集至少有 2 個元素 , 且每個子集中任意兩個元素之差的絕對值均大于1A的子集個數為 _. ”的16. 設集合 A1,2, ,10 , 則滿足“每個子集至少有2 個元素 , 且每個子集中任意兩個元素之差的絕對值均大于 1. ”的 A 的子集個數 _.17. 質點 X 按以下規則在A, B 兩點間移動 : 規則 : 若質點 X 在 B 處 , 則一秒后必移到A 處；規則 : 若質點 X 在 A 處 , 則一秒后分別以1

6、 的概率移到 A 處或 B 處 . 現在 , 質點 X 在 A 處 , 求“第 n 秒質點 X 在 A2處”的概率 .18. 用“ 1 2 ”紙牌若干張 , 放在一個圖形上 , 要求“不空、不超、不重疊” , 滿足這種條件的叫做一種“完全覆蓋” . 問用“ 1 2 ”紙牌 , 覆蓋“ 2 n ”圖形有多少種覆蓋方法？19. 已知集合 A 1,2,3,4 . 若每次從 A 中隨機地取出一個數 ( 可以重復取數 ), 當某一次取出的數與上一次取出的數之和為質數時 , 停止取數 , 求最后一次取到的數是 1的概率 .20.設十進制 n 位正整數中任何相鄰兩位數字( 從左至右 ) 不出現 12 的數有

7、 an 個 .(1)求 an 的表達式；(2) 求證 :1 (an 1an1) 是完全平方數 .2第2頁共8頁組合計數問題的基本方法遞推(教師版 )一、基礎問題呈現1.欲登上第10級臺階 ,若每步只能跨上一級或兩級, 則不同上臺階的方法數為【C 】 .A.144B.122C.89D.552.五個人排成一列, 重新站隊時 , 若各人都不站在原來的位置上, 則不同站隊的方法數為【B 】 .A.60B.44C.36D.243. 若用四種不同顏色給四邊形的四 n 個頂點染色 , 每點染一種顏色 , 相鄰的頂點染不同的顏色 , 則不同的染色方法數為【 A 】 .A.84B.72C.48D.244. 甲、

8、乙、丙、丁四人相互傳球, 第一次甲傳給乙、丙、丁中的任一人, 第二次由拿球者再傳給其他人中任一人 , 這樣共傳了四次 , 則第四次球恰傳回到甲的方法數為【D 】.A.42B.27C.24D.215. 甲、乙二人拿兩顆骰子做拋擲游戲 , 規則如下 : 若擲出的點數之和為 3 的倍數時 , 原擲骰子的人再繼續擲；若擲出的點數不是3 的倍數時就由對方接著擲. 若第一次由甲開始擲, 則第六次恰由甲擲的概率為【 D 】.365364122121A.B.C.D.729729243243二、推廣問題解決6. 欲登上第 n (n N * ) 級樓梯 , 如果每步只能跨上一級或兩級 , 求不同的方法數 .解：

9、設走 n 級有 an 種走法 , 這些走法可按第一步來分類,第一類 : 第一步是一步一級, 則余下的 n1 級有 an 1 種走法；第二類 : 第一步是一步兩級, 則余下的 n2級有 an 2 種走法 ,所以 anan 1 an 2 , 又易得 a1 1, a22, 由遞推可得 an .注：在數列 an 中 , a1 1, a22 , 且 anan 1an2 , 求 an .7. 已知 n (nN * ) 個人排成一列 , 重新站隊時 , 各人都不站在原來的位置上, 求不同的方法數 .解： 設滿足條件的站隊方式有an 種 , 現在通過合理分步, 恰當分類來找出遞推關系 :第一步 : 第一個人不

10、站在原來的第一個位置, 有 n1種站法 .第3頁共8頁第二步 : 假設第一個人站在第二個位置, 則第二個人的站法又可以分為兩類: 第一類 , 第二個人恰好站在第一個位置 , 則余下的 n 2個人有 an2 種站隊方式；第二類 , 第二個人不站在第一個位置, 則就是第二個人不站在第一個位置,第三個人不站在第三個位置, 第四個人不站在第四個位置, 第 n 個人不站在第 n 個位置 , 所以有 an1 種站隊方式 .由分步計數原理和分類計數原理, 便可得遞推關系 :an ( n 1)(an 2 an1 ) , 顯然 , a10, a21, 由遞推可得 an .注：在數列 an 中 , a10, a2

11、1, 且 an(n 1)(an 2an 1 ) , 求 an .8. 用 m (m 3) 種不同顏色給n ( n 3) 邊形 A1 A2An 的 n 個頂點染色 , 每點染一種顏色 , 相鄰的頂點染不同的顏色 , 求不同的染色方法數 .解： 設不同的染色方法有an 種 , 現在通過合理分布, 恰當分類來找出遞推關系:第一步 : 染 A1 , 有 m種染法；第二步 : 染 A2 , 有 m1種染法；同理 , 染 A3 , , An 1 均有 m1種染法；最后染 An , 若 An 與 An 1 不同色 , 則仍有 m 1種染法 , 相乘得 m(m 1)n1種染法 , 但要去掉 An 與 A1同色

12、的染法數 , 此時將 An 與 A1 看成一個點 , 得出需要排除的染法數為an 1 , 故有 anm(m1) n 1an 1 .由遞推可得 an .注：在數列 an 中 , a31 m( m1)(m2) , 且 anm( m 1) n 1an 1 (n4) , 求 an (n3) .69. 有 m(m N * ) 個人相互進行 n(n N * ) 次傳球 , 由甲先傳 , 第一次甲傳給其他m 1 個人中的任一人 , 第二次由拿球者再傳給其他人中任一人, 求這樣經過 n 次傳球 , 球回到甲手中的傳球方法數 .解： 設不同的傳球方法共有 an 種 , 現在我們來通過合理分步 , 恰當分類找出遞

13、推關系:第一步進行第一次傳球: 甲傳給其他人 , 有 m1 種傳球方法；第二步進行第二次傳球: 拿球者把球傳給其他人, 仍有 m1 種傳球方法；同理 , 第三次、第四次、 、第 n1次傳球都有 m 1種傳球方法；最后進行第 n 次傳球 , 由于只能傳給甲,故只有一次傳球方法 , 相乘得 ( m1) n 1 種傳球方法 , 但要注意第 n1 次傳球不能傳給甲 , 否則就不存在第n 次傳球 , 因此要去掉第 n 1次傳球 , 球恰好傳給甲的傳球方第4頁共8頁法數 , 這就是由甲先傳, 經過n 1次傳球后球又回到甲手中的傳球方法, 顯然 , 這里有 an 1 種傳球方法 , 故有遞推關系 : an

14、(m1) n 1an1 , 由遞推可得 an .注：在數列 an 中 ,a10 ,且 an(m 1)n 1an 1 ( n 2) , 求 an .10. 甲、乙二人拿兩顆骰子做拋擲游戲 , 規則如下 : 若擲出的點數之和為 3的倍數時 , 原擲骰子的人再繼續擲 .若擲出的點數不是3 的倍數時就由對方接著擲, 第一次由甲開始擲 , 求第 n 次仍由甲擲的概率Pn .解： 連續擲兩次骰子 , 點數之和為 3的倍數的概率為 12112, 不是 3 的倍數的概率為 1, 又第 n 次36333由甲擲這一事件 , 包括第 n1 次由甲擲 , 第 n 次繼續由甲擲這一事件以及第n 1 次由乙擲 , 第 n

15、 次由甲擲這一事件 , 并且這兩個事件是互斥的, 而第 n1 次由甲擲的概率為 Pn 1 ,由乙擲的概率為 1Pn 1 , 故有遞推關系 Pn1 Pn 12 (1Pn 1 )2 Pn 12 ,(n 2, nN ),又P1 1111, 從而有 Pn(Pn 1) ,3333232由遞推可得 Pn .( 事實上 ,Pn1 1( 1)n 1 ).23三、能力問題測評11. 如圖 , 將 A, B, C , D , E, F 這六個區域著四種不同的顏色, 每個區域著一種顏色 , 且相EDAFC鄰區域著不同的顏色, 不同著色方法數為_.120B12.由 0 和 1組成的長度為 n 的排列中 , 沒有兩個

16、1相連的排列個數記為 an ( 例如 , 排列 00101,10010的長度均為 5 ), 則 a8 _.5513.現有甲、 乙兩人輪流擲一枚質地均勻的正方體骰子, 規定 : 如果某人某一次擲出 1點 , 那么下一次就繼續由此人擲；如果某人擲出的是其他的點數, 那么就由另一個人來擲. 若第一次由甲擲, 則第 n 次仍由甲擲的概率為 _.11 (2) n 12 314. 從集合 A 1,2,3,4 中任取五個數 ( 可重復 ) 排成一個五位數 , 要求首位只能排 1, 且任意相鄰兩位置不能排同一數 , 則末位恰也是1的五位數的個數為_.2115. 若設集合 A 1,2, ,10 , 則滿足 “每

17、個子集至少有 2 個元素 , 且每個子集中任意兩個元素之差的絕對1A的子集個數為 _.值均大于 . ”的解：設 an 為集合 1,2,n 的符合題意的子集個數, 則 1,2, k, k1, k 2 的符合題意的子集可分為兩類 : 第一類子集中不含 k2 , 這類子集有 ak 1 個；第二類子集含k2 , 這類子集或為 1,2, , k 的相應子第5頁共8頁集與 k2 的并 , 或為 1,2,k 的單元子集與 k2 的并 , 共有 akk 個 . 故 ak 2ak 1akk . 又由于 a3 1, a4 3 , 從而遞推可得 a10 133 .16. 若設集合 A 1,2, ,10 , 則滿足

18、“每個子集至少有 2 個元素 , 且每個子集中任意兩個元素之差的絕對值均大于1A的子集個數為 _. ”的解：設 an 為集合 1,2,n 的符合題意的子集個數, 則 1,2, k, k1, k 2 的符合題意的子集可分為兩類 : 第一類子集中不含 k2, 這類子集有 ak 1 個；第二類子集含k 2 , 這類子集或為 1,2, k 的相應子集與 k2 的并 , 或為 1,2,k 的單元子集與 k2的并,共有 akk 個 . 故 ak 2 ak 1ak k . 又由于 a3 1, a4 3 , 從而遞推可得 a10 133 .17. 質點 X 按以下規則在A, B 兩點間移動 : 規則 : 若質

19、點 X 在 B 處 , 則一秒后必移到A 處；規則 : 若質點 X 在 A 處 , 則一秒后分別以1 的概率移到 A 處或 B 處 . 現在 , 質點 X 在 A 處 , 求“第 n 秒質點 X 在 A2處”的概率 .解：設“第 n 秒質點 X 在 A 處”的概率為pn , 則“第 n 秒質點 X 在 B 處” 的概率為 1pn . 因為第 n1秒質點 X 在 A 處的事件包括兩種情況: 第 n 秒在 A 處 , 且第 n1 秒在 A 處；第 n 秒在 B 處 , 且第 n1秒在A 處；故 pn 11 pn (1 pn ) 1 1 pn , 又由題意易得 p1 1 , 從而有 pn 1 2 (

20、 1 )n .2223218. 用“ 1 2 ”紙牌若干張 , 放在一個圖形上 , 要求“不空、不超、不重疊” , 滿足這種條件的叫做一種“完全覆蓋” . 問用“ 1 2 ”紙牌 , 覆蓋“ 2 n ”圖形有多少種覆蓋方法？解： 直接畫出所有“完全覆蓋”方法, 是很困難的 . 我們還是從簡單情況入手, 歸納規律 .用“ 1 2 ”紙牌覆蓋“ 2 1 ”圖 , 只有一種覆蓋方法；用“1 2 ”紙牌覆蓋“ 22 ”圖 , 有兩種覆蓋方法.用“ 12”紙牌覆蓋“2 3”圖, 有三種方法 .“豎,豎, 豎”,“豎, 橫,橫” ,“橫, 橫, 豎”. 通過分析發現 , “ 23 ”的覆蓋方法數正好等于“

21、2 1”與“ 22 ”的覆蓋方法數之和. 這是為何呢？當第一張牌豎放時 , 剩下“ 22 ”圖 , 有兩種方法；當第一張橫放時, 第二張也必須橫放, 剩下“ 21”圖 , 有一種放法 , 這說明“ 23”圖可轉化為“22 ”或 2 1”圖 . 同理 , “ 24”圖可轉化成“23”圖形 ( 第一張豎放)或“ 2 2”圖形 ( 第一、二張橫放), 依此類推 . 若設“ 2 n ”圖形用“ 12 ”紙牌覆蓋有 an 種方法 , 則有 an an 1an 2 , 故由遞推可求得an ( “ 2 n ”圖 ) 的覆蓋數 .19. 已知集合 A 1,2,3,4 . 若每次從 A 中隨機地取出一個數 (

22、可以重復取數 ), 當某一次取出的數與上一次取出的數之和為質數時 , 停止取數 , 求最后一次取到的數是 1的概率 .第6頁共8頁解： 不妨把所取的數排成一列, 設以“i”開頭以“”結尾的數列出現的概率為pi (i 1,2,3,4) , 則如果1一個數列以“1”開頭 , 即是說第一次選取的數為“1, 故第一次選取“1” , 由于每一次選取均是隨機的的概率為1 . 在第一次選到 “ 1”后 , 如果第二次選取的是 “ 1”, 那么取數就結束 , 此時以 “ 1”開頭以 “ 1”4結尾；如果第二次選取的是“2”, 由1 23 為質數知取數結束,但此時不是以“ 1”結尾的數列；如果第二次選取的是“

23、3 ” , 由 134 不是質數知取數不能結束, 此時要“ 1”結尾的概率就為p3 了 ( 這里用了轉化的思想 , 丟掉了對末尾的討論) ；如果第二次選取的是“ 4”,由145 為質數知取數結束 , 但此時111”結尾的事件包括兩個互斥事件: 第一個數不是以“ ”結尾的數列 .由以上分析可知 : 以“ ”開頭以“是“1” , 且第二個數是“11” , 且第二個數是“3”, 并以“1”結尾 .”；第一個數是“從而 , 可得 : p1 (1p ) .1443同理 , 可得 : p21 ( 1p2p4 ) ； p31 ( p1 p3 ) ； p41( 1p2p4 ) .44444:p131, p31p41.由以上四個等式可求得, p28,84444所以 , 最后一次取到的數是1的概率為 p1p2p3 p4311115448448.4420. 設十進制 n 位正整數中任