排列組合中關(guān)于捆綁法、插空法、插隔板法的應(yīng)用 (1)[致遠(yuǎn)書屋]

1、排列組合中關(guān)于捆綁法、插空法、插隔板法的應(yīng)用捆綁法：當(dāng)要求某幾個(gè)元素必須相鄰（挨著）時(shí)，先將這幾個(gè)元素看做一個(gè)整體，（比如：原來3個(gè)元素，整體考慮之后看成1個(gè)元素）然后將這個(gè)整體和其它元素進(jìn)行考慮。這時(shí)要注意：一般整體內(nèi)部各元素如果在前后順序上有區(qū)別的還需進(jìn)行一定的順序考慮。插空法：當(dāng)要求某幾個(gè)元素必須不相鄰（挨著）時(shí)，可先將其它元素排好，然后再將要求不相鄰的元素根據(jù)題目要求插入到已排好的元素的空隙或兩端位置。插隔板法：指在解決若干相同元素分組，要求每組至少一個(gè)元素時(shí)，采用將比分組數(shù)目少1的隔板插入到元素中的一種解題策略。題目特點(diǎn)：“若干相同元素分組”、“ 每組至少一個(gè)元素”。例1：一張節(jié)目表

2、上原有3個(gè)節(jié)目，如果保持這3個(gè)節(jié)目的相對(duì)順序不變，再添進(jìn)去2個(gè)新節(jié)目，有多少種安排方法？ A.20 B.12 C.6 D.4分兩種情況考慮1、這兩個(gè)新節(jié)目挨著，那么三個(gè)節(jié)目有4個(gè)空，又考慮到這兩個(gè)節(jié)目的先后順序共有2=8種2、這兩個(gè)節(jié)目不挨著，那么三個(gè)節(jié)目有4個(gè)空，這就相當(dāng)于考慮兩個(gè)數(shù)在4個(gè)位置的排列，由=12種綜上得，共8+12=20種 此題中使用了捆綁法和插空法。例2：A、B、C、D、E五個(gè)人排成一排，其中A、B兩人不站一起，共有（ ）種站法。A.120B.72 C.48D.24插空法:我們來這樣考慮，因A、B兩人不站一起，故可考慮的位置C、D、E，C、D、E三個(gè)人站在那有一共留出4個(gè)空，

3、將A、B分別放入這4個(gè)空的不同的空中，那就是4個(gè)空中取2個(gè)空的全排列，即=12。這樣考慮了之后，還有一點(diǎn)就是C、D、E三個(gè)人也存在一個(gè)排列問題，即=6，綜上，共有6*12=72種例3：A、B、C、D、E五個(gè)人排成一排，其中A、B兩人必須站一起，共有（ ）種站法。A.120B.72 C.48D.24捆綁法：此題和上一題實(shí)質(zhì)是一樣的，我們來這樣考慮，A、B兩人既然必須站在一起，那么索性我們就把他們看成一個(gè)人，那么我們就要考慮其和C、D、E共4個(gè)人的全排列，即=24，又因?yàn)锳、B兩人雖然是站在一起了，但還要考慮一個(gè)誰在前誰在后的問題，這有兩種情況，也就是=2，綜上，共有48種。例4：將8個(gè)完全相同的

4、球放到3個(gè)不同的盒子中，要求每個(gè)盒子至少放一個(gè)球，一共有多少種方法？A. 20B.21 C.23D.24插隔板法：解決這道題只需將8個(gè)球分成三組，然后依次將每一個(gè)組分別放到一個(gè)盒子中即可。8個(gè)球分成3個(gè)組可以這樣，用2個(gè)隔板插到這8個(gè)球中，這樣就分成了3個(gè)組。這時(shí)我們考慮的問題就轉(zhuǎn)化成了我們?cè)?個(gè)球的空隙中放2個(gè)隔板有多少種放法的問題。8個(gè)球有7個(gè)空隙，7個(gè)空隙要放2個(gè)隔板，就有種放法，即21種.例5：有9顆相同的糖，每天至少吃1顆，要4天吃完，有多少種吃法？A. 20B.36C.45D.56插隔板法：原理同上，只需用3個(gè)隔板放到9顆糖形成的8個(gè)空隙中，即可分成4天要吃的。就有=56種。不鄰問

5、題插板法解題要點(diǎn)“不鄰問題”插板法先排列，再插空“不鄰問題”插空法，即在解決對(duì)于某幾個(gè)元素要求不相鄰問題時(shí)，先將其它元素排好，再將指定的不相鄰的元素插入已排好元素的間隙或兩端位置，從而將問題解決的策略。例1：若有A、B、C、D、E五個(gè)人排隊(duì)，要求A和B兩個(gè)人必須不站在一起，則有多少排隊(duì)方法?【解析】題目要求A和B兩個(gè)人必須隔開。首先將C、D、E三個(gè)人排列，有種排法;若排成DCE，則D、C、E“中間”和“兩端”共有四個(gè)空位置，也即是：DCE，此時(shí)可將A、B兩人插到四個(gè)空位置中的任意兩個(gè)位置，有種插法。由乘法原理，共有排隊(duì)方法：。例2：在一張節(jié)目單中原有6個(gè)節(jié)目，若保持這些節(jié)目相對(duì)順序不變，再添加

6、進(jìn)去3個(gè)節(jié)目，則所有不同的添加方法共有多少種?【解析】直接解答較為麻煩，可利用插空法去解題，故可先用一個(gè)節(jié)目去插7個(gè)空位(原來的6個(gè)節(jié)目排好后，中間和兩端共有7個(gè)空位)，有種方法;再用另 一個(gè)節(jié)目去插8個(gè)空位，有種方法;用最后一個(gè)節(jié)目去插9個(gè)空位，有種方法，由乘法原理得：所有不同的添加方法為=504種。例3：一條馬路上有編號(hào)為1、2、9的九盞路燈，為了節(jié)約用電，可以把其中的三盞關(guān)掉，但不能同時(shí)關(guān)掉相鄰的兩盞或三盞，則所有不同的關(guān)燈方法有多少種?【解析】若直接解答須分類討論，情況較復(fù)雜。故可把六盞亮著的燈看作六個(gè)元素，然后用不亮的三盞燈去插7個(gè)空位，共有種方法(請(qǐng)您想想為什么不是)，因此所有不同

7、的關(guān)燈方法有種。【提示】運(yùn)用插空法解決排列組合問題時(shí)，一定要注意插空位置包括先排好元素“中間空位”和“兩端空位”。解題過程是“先排列，再插空”。計(jì)數(shù)之插板法總結(jié)：插板法就是插板法就是在n個(gè)元素間的（n-1）個(gè)空中插入 若干個(gè)（b）個(gè)板，可以把n個(gè)元素分成（b+1）組的方法。應(yīng)用插板法必須滿足三個(gè)條件：（1）這n個(gè)元素必須互不相異（2）所分成的每一組至少分得一個(gè)元素(3)分成的組別彼此相異舉個(gè)很普通的例子來說明：把10個(gè)相同的小球放入3個(gè)不同的箱子，每個(gè)箱子至少一個(gè)，問有幾種情況？問題的題干滿足條件（1）（2），適用插板法，C92=36下面通過幾道題目介紹下插板法的應(yīng)用:a 湊元素插板法 （有些

8、題目滿足條件（1），不滿足條件（2），此時(shí)可適用此方法）1 ：把10個(gè)相同的小球放入3個(gè)不同的箱子，問有幾種情況？2： 把10個(gè)相同小球放入3個(gè)不同箱子，第一個(gè)箱子至少1個(gè)，第二個(gè)箱子至少3個(gè)，第三個(gè)箱子可以放空球，有幾種情況？b 添板插板法3：把10個(gè)相同小球放入3個(gè)不同的箱子，問有幾種情況？4：有一類自然數(shù)，從第三個(gè)數(shù)字開始，每個(gè)數(shù)字都恰好是它前面兩個(gè)數(shù)字之和，直至不能再寫為止，如257，1459等等，這類數(shù)共有幾個(gè)？5：有一類自然數(shù)，從第四個(gè)數(shù)字開始，每個(gè)數(shù)字都恰好是它前面三個(gè)數(shù)字之和，直至不能再寫為止，如2349，1427等等，這類數(shù)共有幾個(gè)？答案：1、3個(gè)箱子都可能取到空球，條件（2

9、）不滿足，此時(shí)如果在3個(gè)箱子種各預(yù)先放入1個(gè)小球，則問題就等價(jià)于把13個(gè)相同小球放入3個(gè)不同箱子，每個(gè)箱子至少一個(gè)，有幾種情況？顯然就是 c12 2=662、我們可以在第二個(gè)箱子先放入10個(gè)小球中的2個(gè)，小球剩8個(gè)放3個(gè)箱子，然后在第三個(gè)箱子放入8個(gè)小球之外的1個(gè)小球，則問題轉(zhuǎn)化為 把9個(gè)相同小球放3不同箱子，每箱至少1個(gè)，幾種方法？ c8 2=283、-o - o - o - o - o - o - o - o - o - o - o表示10個(gè)小球，-表示空位,11個(gè)空位中取2個(gè)加入2塊板，第一組和第三組可以取到空的情況，第2組始終不能取空,此時(shí) 若在 第11個(gè)空位后加入第12塊板，設(shè)取到該板時(shí)，第二組取球?yàn)榭?則每一組都可能取球?yàn)榭?c12 2=664、因?yàn)榍?位數(shù)字唯一對(duì)應(yīng)了符合要求的一個(gè)數(shù)，只要求出前2位有幾種情況即可，設(shè)前兩位為ab顯然a+b=9 ,且a不為0 1 -1- 1 -1 -1 -1 -1 -1 -1 - - 。 1代表9個(gè)1，-代表10個(gè)空位我們可以在這9個(gè)空位中插入2個(gè)板，分成3組，第一組取到a個(gè)1，第二組取到b個(gè)1，但此時(shí)第二組始終不能取空，若多添加第10個(gè)空時(shí)，設(shè)取到該板時(shí)第二組取空，即b=0，所以一共有 =455、類似的，某數(shù)的前三位為abc，a+b+c=9