隔板法小结

参考文档->

因为搞初赛时一直很懵逼于是就随便写了一点 :)

1.简单问题

约束:

元素无差异,容器(组别)有差异,每个容器(组别)不能为空(相当于没限制)。

问题:

例1:将10个相同小球放入3个不同箱子,每个箱子至少一个,问方案数?

解析:O[]O[]O[]O[]O[]O[]O[]O[]O[]O,10个小球排成一排,中间有9个空,现在分成3份,相当于选2个隔板,所以方案数为(C_9^2=36)种。

总结:

ps:为了方便下面的描述,将本问题用二元组(Base(n,b))表示,意义是将n个相同的球放入b个不同箱子中,每个箱子不能为空的方案数。

通式为(Base(n,b)=C_{n-1}^{b-1}),意义是在n-1个板子中选择b-1个。

2.变式-凑元素法

约束:

元素无差异,容器(组别)有差异,容器(组别)可以为空有个数限制

问题:

例1:将10个相同小球放入3个不同箱子可以有箱子为空,问方案数?

解析

这个问题其实等价于Base(13,3)。如何理解呢?拿13个球去填,保证每个箱子都有一个球,那么会有10个余下的球可以随便填,而这就等价于我们当前的问题。

所以答案为(C_{12}^2=66)种。

例2:一共16个一样的苹果,要分给4只编号分别为1,2,3,4的猴子,要求每只猴子的苹果数不少于他们各自的编号,问方案数?

解析

预先分给第1只猴0个,第2只猴子1个,第3只猴子2个,第4只猴子3个。这样还剩下10个苹果随便分,问题等价于Base(10,4)所以答案为(C_9^3=84)

例3:把10个相同小球放入3个不同箱子,第一个箱子至少1个,第二个箱子至少3个,第三个箱子可以空着,问方案数。

解析

第二个箱子中先给它放2个。第三个箱子中额外准备1个球。所以总共还有9个球,问题等价于Base(9,3),所以方案数为(C_8^2=28)种。

总结:

根据每个容器的约束条件(可为空,至少放几个)来对元素个数进行调整,再转化成上面最基础的问题求解。

一般情况下可以做出如下转化:有(k)个箱子不能为空->多准备(k)个球总球数增加(k)个,某个箱子至少得放(k)个->先给他放(k-1)个,从总球数中减去(k-1)个。

3.变式-添插板法

问题:

仍然是原来的问题,我们换一种方式去分析。

例1:将7个相同小球放入4个不同箱子可以有箱子为空,问方案数?

解析

我们试试看能不能直接通过加插板的方式来解决问题。

[]O[]O[]O[]O[]O[]O[]O[],这样子构造就有7个球,8个板子。我们在这之中选择两个板子,可以表示出箱子1,箱子4的分划情况,但对于箱子2,箱子3我们无法表示它们为空的状态(不然就有两个板子重在一起了),所以在所有板子后面在多加两个板子,占了第一个板子表示箱子2为空,占了第二个板子表示箱子3为空。

像这样子[]O[]O[]O[]O[]O[]O[]O[][add1][add2]。这样我们只用在总共10个板子中选择3个板子。所以答案为(C_{10}^3=120)

比如当分类情况为{(2,3,1,1)}时状态为[]O[]O[✔]O[]O[]O[✔]O[✔]O[][][]

当分类情况为{(0,3,0,4)}时状态为[✔]O[]O[]O[✔]O[]O[]O[]O[][][✔];

当分类情况为{(1,0,6,0)}时状态为[]O[✔]O[]O[]O[]O[]O[]O[✔][✔][]。

4.应用

很多分组计数问题都可以通过转化成隔板模型去简化理解,不一定会出现上面提到的容器之类的,但同样可以建立隔板模型。具体问题具体分析,根据意义来走就好了。

例1:一共10颗糖,每天至少吃1粒,吃完为止,问方案数?

解析

建立隔板模型O_O_O_O_O_O_O_O_O_O,由于没有限定天数,所以也就没有所谓的容器了,一共9个板子,都可以选择,所以方案数为(2^9=512)

例2:一共15块糖,每天至少吃3块,吃完为止,问方案数?

解析

好像不能简单的按上面思路去分析了,因为它一天至少要吃3块。联想到之前分析过得“凑元素法”,但“凑元素法”需要容器个数,而这里没有天数——也就是容器。

那我们就枚举天数呗,然后根据加法原理将所有情况相加即可。根据题意可知天数(t∈[1,5])

当t=1或5时,(ways=1+1=2)
当t=2时,每天都预先吃2块,还剩11块,所以(ways=Base(11,2)=C_{10}^1=10)
当t=3时,每天都预先吃2块,还剩9块,所以(ways=Base(9,3)=C_{8}^2=28)
当t=4时,每天都预先吃2块,还剩7块,所以(ways=Base(7,4)=C_{6}^3=20)

相加得(1+1+10+28+20=60)种。

例3:一列队伍原有6个人,现在有三个人A,B,C来插队,问最后形成队伍的方案数?

多次插板。

一开始的队伍情况可以这样表示_O_O_O_O_O_O_,一共6个球,7个板,任选一个板子往上面放A,方案数为(C_7^1)。放上一个人之后增加一个球,一个板,变成7个球,8个版,所以B的插队方式数(C_8^1)。类似的C的插队方式数位(C_9^1)

根据乘法原理答案为(C_7^1*C_8^1*C_9^1=504)种。

原文地址:https://www.cnblogs.com/Tieechal/p/11644376.html