高中數(shù)學 第一章 計數(shù)原理 1.4 計數(shù)應用題 隔板法在排列組合中的應用素材 蘇教版選修23.doc

隔板法在排列組合中的應用在排列組合中，對于將不可分辨的球裝入到可以分辨的盒子中而求裝入方法數(shù)的問題，常用隔板法。例1. 求方程x+y+z=10的正整數(shù)解的個數(shù)。分析將10個球排成一排，球與球之間形成9個空隙，將兩個隔板插入這些空隙中（每空至多插一塊隔板），規(guī)定由隔板分成的左、中、右三部分的球數(shù)分別為x、y、z之值（如下圖）。則隔法與解的個數(shù)之間建立了一一對立關(guān)系，故解的個數(shù)為c92=36（個）。實際運用隔板法解題時，在確定球數(shù)、如何插隔板等問題上形成了一些技巧。下面舉例說明。技巧一：添加球數(shù)用隔板法。 例2. 求方程x+y+z=10的非負整數(shù)解的個數(shù)。分析注意到x、y、z可以為零，故上題解法中的限定“每空至多插一塊隔板”就不成立了，怎么辦呢？只要添加三個球，給x、y、z各一個球。這樣原問題就轉(zhuǎn)化為求x+y+z=13的正整數(shù)解的個數(shù)了，故解的個數(shù)為c122=66（個）。點評本例通過添加球數(shù)，將問題轉(zhuǎn)化為如例1中的典型隔板法問題。技巧二：減少球數(shù)用隔板法：例3. 將20個相同的小球放入編號分別為1，2，3，4的四個盒子中，要求每個盒子中的球數(shù)不少于它的編號數(shù)，求放法總數(shù)。解法1：先在編號1，2，3，4的四個盒子內(nèi)分別放0，1，2，3個球，剩下14個球，有1種方法；再把剩下的球分成4組，每組至少1個，由例1知方法有c133=286（種）。解法2：第一步先在編號1，2，3，4的四個盒子內(nèi)分別放1，2，3，4個球，剩下10個球，有1種方法；第二步把剩下的10個相同的球放入編號為1，2，3，4的盒子里，由例2知方法有c133=286（種）。點評兩種解法均通過減少球數(shù)將問題轉(zhuǎn)化為例1、例2中的典型問題。技巧三：先后插入用隔板法。例4. 為宣傳黨的十六大會議精神，一文藝團體下基層宣傳演出，準備的節(jié)目表中原有4個歌舞節(jié)目，如果保持這些節(jié)目的相對順序不變，擬再添兩個小品節(jié)目，則不同的排列方法有多少種？分析記兩個小品節(jié)目分別為a、b。先排a節(jié)目。根據(jù)a節(jié)目前后的歌舞節(jié)目數(shù)目考慮方法數(shù)，相當于把4個球分成兩堆，由例2知有c51種方法。這一步完成后就有5個節(jié)目了。再考慮需加入的b節(jié)目前后的節(jié)目數(shù)，同理知有c61種方法。故由分步計數(shù)原理知，方法共有c51* c61 (種)。點評對本題所需插入的兩個隔板采取先后依次插入的方法，使問題得到巧妙解決。解答排列組合問題，首先必須認真審題，明確是屬于排列問題還是組合問題，或者屬于排列與組合的混合問題，其次要抓住問題的本質(zhì)特征，靈活運用基本原理和公式進行分析，同時還要注意講究一些策略和方法技巧。下面介紹幾種常用的解題方法和策略。解決排列組合問題有幾種相對比較特殊的方法。下面通過例題逐個掌握：一、相鄰問題-捆綁法 不鄰問題-插空法對于某幾個元素不相鄰的排列問題，可先將其他元素排好，再將不相鄰元素在已排好的元素之間及兩端空隙中插入即可?！纠}1】一張節(jié)目表上原有3個節(jié)目，如果保持這3個節(jié)目的相對順序不變，再添進去2個新節(jié)目，有多少種安排方法?a.20 b.12 c.6 d.4【答案】a?！窘馕觥渴紫龋瑥念}中之3個節(jié)目固定，固有四個空。所以一、兩個新節(jié)目相鄰的的時候：把它們捆在一起，看成一個節(jié)目，此時注意：捆在一起的這兩個節(jié)目本身也有順序，所以有：c(4，1)2=42=8種方法。二、兩個節(jié)目不相鄰的時候：此時將兩個節(jié)目直接插空有：a(4，2)=12種方法。綜上所述，共有12+8=20種。二、插板法一般解決相同元素分配問題，而且對被分成的元素限制很弱(一般只要求不等于零)，只對分成的份數(shù)有要求?！纠}2】把20臺電腦分給18個村，要求每村至少分一臺，共有多少種分配方法?a.190 b.171 c.153 d.19【答案】b。【解析】此題的想法即是插板思想：在20電腦內(nèi)部所形成的19個空中任意插入17個板，這樣即把其分成18份，那么共有： c(19，17)=c(19，2)=171 種。三、特殊位置和特殊元素優(yōu)先法對有限制的排列組合問題中的特殊元素或特殊位置優(yōu)先考慮?！纠}2】從6名運動員中選4人參加4100米接力，甲不跑第一棒和第四棒的參賽方案各有多少種?a.120 b.240 c.180 d.60【答案】b?！窘馕觥糠椒ㄒ唬禾厥馕恢脙?yōu)先法：首先填充第一棒，第一棒共有5個元素可供選擇，其次第4棒則有4個元素可以選擇;然后第2棒則有4個元素可以選擇，第3棒則有3個元素可以選擇。則共有5443=240種。方法二：特殊元素優(yōu)先法：首先考慮甲元素的位置第一類，甲不參賽有a(5,4)=120種排法;第二類，甲參賽，因只有兩個位置可供選擇，故有2種排法;其余5人占3個位置有a(5,3)=60種占法，故有260=120種方案。所以有120+120=240種參賽方案。四、逆向考慮法對于直接從正面算比較復雜的排列、組合題，我們就要學會間接的方法。正方體8個頂點中取出4個，可組成多少個四面體?a.70 b.64 c.61 d.58【答案】d。【解析】所求問題的方法數(shù)=任意選四點的組合數(shù)-共面四點的方法數(shù)，共c(8，4)-12=70-12=58個。五、分類法解含有約束條件的排列組合問題，應按元素性質(zhì)進行分類，按事情發(fā)生的連續(xù)過程分步，保證每步獨立，達到分類標準明確，分步層次清楚，不重不漏?！纠}3】五個人排成一排，其中甲不在排頭，乙不在排尾，不同的排法有a.120種 b.96種 c.78種