隔板法在排列組合中的應(yīng)用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上在排列組合中，對(duì)于將不可分辨的球裝入到可以分辨的盒子中而求裝入方法數(shù)的問題，常用隔板法。例1. 求方程X+Y+Z=10的正整數(shù)解的個(gè)數(shù)。分析將10個(gè)球排成一排，球與球之間形成9個(gè)空隙，將兩個(gè)隔板插入這些空隙中（每空至多插一塊隔板），規(guī)定由隔板分成的左、中、右三部分的球數(shù)分別為x、y、z之值（如下圖）。則隔法與解的個(gè)數(shù)之間建立了一一對(duì)立關(guān)系，故解的個(gè)數(shù)為C92=36（個(gè)）。實(shí)際運(yùn)用隔板法解題時(shí)，在確定球數(shù)、如何插隔板等問題上形成了一些技巧。下面舉例說明。技巧一：添加球數(shù)用隔板法。       

2、0;     例2. 求方程X+Y+Z=10的非負(fù)整數(shù)解的個(gè)數(shù)。分析注意到x、y、z可以為零，故上題解法中的限定“每空至多插一塊隔板”就不成立了，怎么辦呢？只要添加三個(gè)球，給x、y、z各一個(gè)球。這樣原問題就轉(zhuǎn)化為求X+Y+Z=13的正整數(shù)解的個(gè)數(shù)了，故解的個(gè)數(shù)為C122=66（個(gè)）。點(diǎn)評(píng)本例通過添加球數(shù)，將問題轉(zhuǎn)化為如例1中的典型隔板法問題。技巧二：減少球數(shù)用隔板法：例3. 將20個(gè)相同的小球放入編號(hào)分別為1，2，3，4的四個(gè)盒子中，要求每個(gè)盒子中的球數(shù)不少于它的編號(hào)數(shù)，求放法總數(shù)。解法1：先在編號(hào)1，2，3，4的四個(gè)盒子內(nèi)分別放0，1，2，3個(gè)球，剩下

3、14個(gè)球，有1種方法；再把剩下的球分成4組，每組至少1個(gè)，由例1知方法有C133=286（種）。解法2：第一步先在編號(hào)1，2，3，4的四個(gè)盒子內(nèi)分別放1，2，3，4個(gè)球，剩下10個(gè)球，有1種方法；第二步把剩下的10個(gè)相同的球放入編號(hào)為1，2，3，4的盒子里，由例2知方法有C133=286（種）。點(diǎn)評(píng)兩種解法均通過減少球數(shù)將問題轉(zhuǎn)化為例1、例2中的典型問題。技巧三：先后插入用隔板法。例4. 為宣傳黨的十六大會(huì)議精神，一文藝團(tuán)體下基層宣傳演出，準(zhǔn)備的節(jié)目表中原有4個(gè)歌舞節(jié)目，如果保持這些節(jié)目的相對(duì)順序不變，擬再添兩個(gè)小品節(jié)目，則不同的排列方法有多少種？分析記兩個(gè)小品節(jié)目分別為A、B。先排A節(jié)目。根

4、據(jù)A節(jié)目前后的歌舞節(jié)目數(shù)目考慮方法數(shù)，相當(dāng)于把4個(gè)球分成兩堆，由例2知有C51種方法。這一步完成后就有5個(gè)節(jié)目了。再考慮需加入的B節(jié)目前后的節(jié)目數(shù)，同理知有C61種方法。故由分步計(jì)數(shù)原理知，方法共有C51* C61 (種)。點(diǎn)評(píng)對(duì)本題所需插入的兩個(gè)隔板采取先后依次插入的方法，使問題得到巧妙解決。解答排列組合問題，首先必須認(rèn)真審題，明確是屬于排列問題還是組合問題，或者屬于排列與組合的混合問題，其次要抓住問題的本質(zhì)特征，靈活運(yùn)用基本原理和公式進(jìn)行分析，同時(shí)還要注意講究一些策略和方法技巧。下面介紹幾種常用的解題方法和策略。解決排列組合問題有幾種相對(duì)比較特殊的方法。下面通過例題逐個(gè)掌握：一、相鄰問題-

5、捆綁法 不鄰問題-插空法對(duì)于某幾個(gè)元素不相鄰的排列問題，可先將其他元素排好，再將不相鄰元素在已排好的元素之間及兩端空隙中插入即可?！纠}1】一張節(jié)目表上原有3個(gè)節(jié)目，如果保持這3個(gè)節(jié)目的相對(duì)順序不變，再添進(jìn)去2個(gè)新節(jié)目，有多少種安排方法?A.20 B.12 C.6 D.4【答案】A?！窘馕觥渴紫?，從題中之3個(gè)節(jié)目固定，固有四個(gè)空。所以一、兩個(gè)新節(jié)目相鄰的的時(shí)候：把它們捆在一起，看成一個(gè)節(jié)目，此時(shí)注意：捆在一起的這兩個(gè)節(jié)目本身也有順序，所以有：C(4，1)×2=4×2=8種方法。二、兩個(gè)節(jié)目不相鄰的時(shí)候：此時(shí)將兩個(gè)節(jié)目直接插空有：A(4，2)=12種方法。綜上所述，共有12+

6、8=20種。二、插板法一般解決相同元素分配問題，而且對(duì)被分成的元素限制很弱(一般只要求不等于零)，只對(duì)分成的份數(shù)有要求?！纠}2】把20臺(tái)電腦分給18個(gè)村，要求每村至少分一臺(tái)，共有多少種分配方法?A.190 B.171 C.153 D.19【答案】B?！窘馕觥看祟}的想法即是插板思想：在20電腦內(nèi)部所形成的19個(gè)空中任意插入17個(gè)板，這樣即把其分成18份，那么共有： C(19，17)=C(19，2)=171 種。三、特殊位置和特殊元素優(yōu)先法對(duì)有限制的排列組合問題中的特殊元素或特殊位置優(yōu)先考慮?！纠}2】從6名運(yùn)動(dòng)員中選4人參加4×100米接力，甲不跑第一棒和第四棒的參賽方案各有多少種?

7、A.120 B.240 C.180 D.60【答案】B?！窘馕觥糠椒ㄒ唬禾厥馕恢脙?yōu)先法：首先填充第一棒，第一棒共有5個(gè)元素可供選擇，其次第4棒則有4個(gè)元素可以選擇;然后第2棒則有4個(gè)元素可以選擇，第3棒則有3個(gè)元素可以選擇。則共有5×4×4×3=240種。方法二：特殊元素優(yōu)先法：首先考慮甲元素的位置第一類，甲不參賽有A(5,4)=120種排法;第二類，甲參賽，因只有兩個(gè)位置可供選擇，故有2種排法;其余5人占3個(gè)位置有A(5,3)=60種占法，故有2×60=120種方案。所以有120+120=240種參賽方案。四、逆向考慮法對(duì)于直接從正面算比較復(fù)雜的排列、組合題，我們就要學(xué)會(huì)間接的方法。正方體8個(gè)頂點(diǎn)中取出4個(gè)，可組成多少個(gè)四面體?A.70 B.64 C.61 D.58【答案】D?！窘馕觥克髥栴}的方法數(shù)=任意選四點(diǎn)的組合數(shù)-共面四點(diǎn)的方法數(shù)，共C(8，4)-12=70-12=58個(gè)。五、分類法解含有約束條件的排列組合問題，應(yīng)按元素性質(zhì)進(jìn)行分類，按事情發(fā)生的連續(xù)過程分步，保證每步獨(dú)立，達(dá)到分類標(biāo)準(zhǔn)明確，分步層次清楚，不重不漏?！纠}3】五個(gè)人排成一排，其中甲不在排頭，乙不在排尾，不同的排法有A.120種 B.96種 C.78種 D.72種【答案】C?！窘馕觥坑深}意可先安排甲，