插板法處理相同元素分配問題

[關鍵詞] 插板法 處理 相同元素 分配

例:8本相同的書分到編號為1、2、3的三個閱覽室，按下列要求各有多少種分配方案?

①每個閱覽室至少有一本書;

②每個閱覽室分到的書不少于其編號數;

③每個閱覽室分到的書不限。

分析:引入隔板模型，將書放成一排，插入2個隔板分成3部分依次分給1、2、3號閱覽室。插法種數就是分配方案數。

相同元素的分配問題是排列、組合中常見的一種題型。處理此類問題一般有兩種方法:一是按要求先分組，然后再分配;二是引入隔板模型，利用“插板法”。

一、先分組，再分配

解:①分組為(6、1、1)，(5、2、1)，(4、3、1)，(4、2、2)，(3、3、2)。

符合條件的分配方案有C13+C13C12+C13C12+C13+C23=21種。

②先將每個閱覽室放入與其編號相同數的書，然后將剩下的2本書進行分組，再分配。分組為(2、0、0)，(1、1、0)。

符合條件的分配方案有C13+C23=6種。

③分組為(8、0、0)，(7、1、0)，(6、2、0)，(6、1、1)，(5、3、0)，

(5、2、1)，(4、4、0)，(4、3、1)，(4、2、2)，(3、3、2)。

符合條件的分配方案有C13+C13C12+C13C12+C13+C13C12+C13C12+C23+C13C12+C13+C23=45種。

二、插板法

解:①為保證三部分都有書，隔板只能向8本書中間的7個空插。共有C25=21種插法;

②方法一:為保證第一部分至少有1本書，第三部分至少有3本書，從第1本書后到倒數第三本書前共有5個空，有C25種插法，由于兩隔板相鄰的插法(中間部分只有1本書)不符合要求，有4種。滿足條件的插法共有C25-4=6種。

方法二:中間部分給編號為1的閱覽室，左、右兩部分分別給編號為2、3的閱覽室。左邊第二本書后到右邊倒數第三本書前共有4個空，有C24=6種插法。

方法三:先分別放入比閱覽室編號小1的書(1號不放，2號放1本，3號放2本)，然后再向剩下的5本書中間4個空插入2個隔板，C24=6種插法。

③方法一:從8本書的9個空插入2個隔板有C29種插法，但不包含兩隔板插在一起(中間部分沒有書)的情況，9個空有9種插法。滿足條件的插法共有C29+9=45種。

方法二:先在8本書9個空插入一隔板，然后再在8本書及一隔板共10個空插入另一隔板，由于兩隔板無序，滿足條件的插法有12×9×10=45種。