隔闆法

隔闆法

組合數學的方法
在組合數學中,隔闆法(又叫插空法)是排列組合的推廣,主要用于解決不相鄰組合與追加排列的問題。隔闆法必須滿足三個條件:這n個元素必須互不相異;所分成的每一組至少分得一個元素;分成的組别彼此相異。[1]
    中文名:隔闆法 外文名: 适用領域: 所屬學科: 别名:插空法

基本内容

隔闆法主要針對的是相同元素的不同分堆問題,可以看成在n個元素間插入(b-1)個闆,即把n個元素分成b組的方法。

允許若幹個人(或位置)為空的問題

例1将20個大小形狀完全相同的小球放入3個不同的盒子,允許有盒子為空,但球必須放完,有多少種不同的方法?

分析:本題中的小球大小形狀完全相同,故這些小球沒有區别,問題等價于将小球分成三組,允許有若幹組無元素,用隔闆法。

解析:将20個小球分成三組需要兩塊隔闆,因為允許有盒子為空,不符合隔闆法的原理,那就人為的再加上3個小球,保證每個盒子都至少分到一個小球,那就符合隔闆法的要求了(分完後,再在每組中各去掉一個小球,即滿足了題設的要求)。然後就變成待分小球總數為23個,球中間有22個空檔,需要在這22個空檔裡加入2個隔闆來分隔為3份,共有C(22,2)=231種不同的方法。

點評:對n件相同物品(或名額)分給m個人(或位置),允許若幹個人(或位置)為空的問題,可以看成将這n件物品分成m組,允許若幹組為空的問題.将n件物品分成m組,需要m-1塊隔闆,将這n件物品和m-1塊隔闆排成一排,占n+m-1位置,從這n+m-1個位置中選m-1個位置放隔闆,因隔闆無差别,故隔闆之間無序,是組合問題,故隔闆有Cn+m-1 m-1種不同的方法,再将物品放入其餘位置,因物品相同無差别,故物品之間無順序,是組合問題,隻有1種放法,根據分步計數原理,共有Cn+m-1 m-1×1=Cn+m-1 m-1種排法。

水果分籃問題

例2:有廣西橘子,煙台蘋果,萊陽梨若幹,從中随意取出四個,問共有多少種不同取法?

問題等價于有四個水果籃,将其分為三組向裡面加入不同水果,且允許籃子為空。

分為三組需要2個隔闆,将水果籃與隔闆并排,隔闆共有4+2個放置位置,故有C(4+2),2個選擇,即15種。

每人(或位置)必須有物品問題

例3将20個優秀學生名額分給18個班,每班至少1個名額,有多少種不同的分配方法?

分析:本題是名額分配問題,用隔闆法。

解析:将20個名額分配給18個班,每班至少1個名額,相當于将20個相同的小球分成18組,每組至少1個,将20個相同的小球分成18組,需要17塊隔闆,先将20個小球排成一排,因小球相同,故小球之間無順序,是組合,隻有1種排法,再在20個小球之間的19個空檔中,選取17個位置放隔闆,因隔闆無差别,故隔闆之間無序,是組合問題,故隔闆有C19、17種不同的放法,根據分步計數原理,共有C19、17種不同的方法,因17塊隔闆将20個小球分成18組,從左到右可以看成每班所得的名額數,每一種隔闆與小球的排法對應于一種分法,故有Cm-1 n-1種分法。

對相同物品分配問題,注意某若幹組能否為空,能為空和不能為不空,方法不同,要體會和掌握。

上一篇:CMM

下一篇:重定向

相關詞條

相關搜索

其它詞條