排列組合問題之插板法.

1、排列組合問題之插板法 :插板法是用于解決“相 同元素”分 組問題,且要求每組均“非 空” 即, 要求每組 至少一個(gè)元素; 若對于“可 空”問 題,即每組可以是零個(gè)元素 ,又該如何解題呢 ?例 1. 現(xiàn)有 10個(gè)完全相同的球全部分給 7個(gè)班級, 每班至少 1個(gè)球, 問共有多少 種不同的分法 ? 【解析】 :題目中球的分法共三類 :第一類:有 3個(gè)班每個(gè)班分到 2個(gè)球,其余 4個(gè)班每班分到 1個(gè)球。其分法種數(shù) 為 C 37=35。第二類:有 1個(gè)班分到 3個(gè)球, 1個(gè)班分到 2個(gè)球,其余 5個(gè)班每班分到 1 個(gè)球。其分法種數(shù) 2* C 27=42。第三類:有 1個(gè)班分到 4個(gè)球,其余的 6個(gè)班每班

2、分到 1個(gè)球。其分法種數(shù) C 17=7。所以, 10個(gè)球分給 7個(gè)班,每班至少一個(gè)球的分法種數(shù)為 84:。由上面解題過程可以明顯感到對這類問題進(jìn)行分類計(jì)算 , 比較繁鎖 , 若是上題中 球的數(shù)目較多處理起來將更加困難 , 因此我們需要尋求一種新的模式解決問題 , 我 們創(chuàng)設(shè)這樣一種虛擬的情境插板。將 10個(gè)相同的球排成一行 , 10個(gè)球之間出現(xiàn)了 9個(gè)空檔, 現(xiàn)在我們用“檔 板” 把 10個(gè)球隔成有序的 7份,每個(gè)班級依次按班級序號分到對應(yīng)位置的幾個(gè)球 (可能 是 1個(gè)、 2個(gè)、 3個(gè)、 4個(gè) ,借助于這樣的虛擬“檔 板”分 配物品的方法稱之為插 板法。由上述分析可知 ,分球的方法實(shí)際上為檔板

3、的插法 :即是在 9個(gè)空檔之中插入 6 個(gè)“檔 板”(6個(gè)檔板可把球分為 7組 ,其方法種數(shù)為 C 39=84。由上述問題的分析解決看到 , 這種插板法解決起來非常簡單 , 但同時(shí)也提醒各位 考友, 這類問題模型適用前提相當(dāng)嚴(yán)格 ,必須同時(shí)滿足以下 3個(gè)條件: 所要分的元素必須完全相同 ; 所要分的元素必須分完 ,決不允許有剩余 ; 參與分元素的每組至少分到 1個(gè),決不允許出現(xiàn)分不到元素的組。下面再給各位看一道例題 :例 2.有 8個(gè)相同的球放到三個(gè)不同的盒子里 ,共有（種不同方法 .A . 35 B . 28 C . 21 D . 45【解析】 :這道題很多同學(xué)錯(cuò)選 C , 錯(cuò)誤的原因是直接

4、套用上面所講的 “插 板 法” 而, 忽略了“插 板法”的 適用條件。例 2和例 1的最大區(qū)別是 :例 1的每組元素 都要求“非 空” 而, 例 2則無此要求,即可以出現(xiàn)空盒子。其實(shí)此題還是用“插 板法” , 只是要做一些小變化 ,詳解如下 :設(shè)想把這 8個(gè)球一個(gè)接一個(gè)排起來 ,即 | | | | | 共 |形成 | 9個(gè) |空檔 |,（此 時(shí)的空檔包括中間 7個(gè)空檔和兩端 2個(gè)空檔 ,然后用 2個(gè)檔板把這 8個(gè)球分成 3組, 先插第一個(gè)檔板 , 由于可以有空盒 ,所以有 9個(gè)空檔可以插 ;再插第二個(gè)板 ,有 10個(gè)空 檔可以插 ,但由于兩個(gè)板是不可分的 （也就是說當(dāng)兩個(gè)檔板相鄰時(shí) ,雖然是兩種插法 , 但實(shí)際上是一種分法 ,所以共 C 210種【提示】 :利用“插 板法”解 決這種相同元素問題時(shí) ,一定要注意“空 ”與 “不 空”的 分析, 防止掉入陷阱?！究偨Y(jié)】 :“非 空”問 題插板法原型為 :設(shè)有 M 個(gè)相同元素,分成 N 組,每組至少 一個(gè)元素的分組方法共有 C N(M-1; “可 空”問 題插板法問題原型為 :設(shè)有 M 個(gè)相同元素 , 分成 N 組,則分組方法共有 C (N-1(M+2 種方法。練習(xí) 1. 有 10級臺階, 分 8步走完。每步可以邁 1級、 2級或 3級臺階, 有多少