古詩詞大全網 - 成語故事 - 排列組合隔板法怎麽用

排列組合隔板法怎麽用

隔板法就是在n個元素間插入(b-1)個板,即把n個元素分成b組的方法。在排列組合中,對於將不可分辨的球裝入到可以分辨的盒子中而求裝入方法數的問題,常用隔板法。

隔板法就是把m個相同單元分配成n組。這樣m個單元中間有m-1個空格,分成n組需要n-1塊隔板,所以就是C(m-1,n-1)種方法。

註意:隔板法的單元必須是相同的。

例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種排法。