巧用隔板法解答组合数学问题

橘子网 5,864 0

在解决组合计数问题中,我们经常会用到一种技巧,叫做“Sticks and Stones”,也有叫做“Stars and Bars”的,美国数学家威廉·费勒(William Feller)在其关于概率的经典著作《概率论及其应用导引》(An Introduction to Probability Theory and Its Applications)中将其普及并推广。这种技巧可用于解决许多简单的计数问题,例如:将n个不可区分的球放入k只可区分的箱子中的方法有多少种?我不知道中文如何翻译合适,暂且译作“隔板法”吧!

让我们从简单的例子开始说起,逐步深入。

例1:Wynne老师手里有10块巧克力,要分给五位小朋友,请问有多少种分法?

我们可以这么思考:假如10块巧克力都分给五位小朋友的其中一个,会有5种分法,即C(5,1);假如每人分两块巧克力,则只有1种分法;假如这五位小朋友中,有一位分到0块,有一位分到1块,有一位分到2块,有一位分到3块,还有一位分到4块,则有5!=120种分法;……等等。

于是,我们可以通过列表枚举的方法得到最终的答案,但看上去有一些复杂,也缺乏数学思维的美感。因此,这里省略五百字。

考虑有4根小棒和10块巧克力。我们发现,通过交换小棒和巧克力的顺序,我们就能得到所有可能的情况。例如下图所示:

巧用隔板法解答组合数学问题

4根小棒加上10快巧克力,一共14件物品,交换顺序就会产生(4+10)!=14!种可能性。又因为这里的4根小棒同质,10快巧克力也是同质的,它们交换顺序会产生重复计数,于是要剔除重复计算的可能性。因此,最终的分法有14!/(4!×10!)=1001种分法。

这里,熟悉组合算法的读者会发现,14!/(4!×10!)=(14×13×12×11)/4!=C(14,4)。巧合?当然不是。

巧用隔板法解答组合数学问题

这个问题还可以换个角度来看。假如有14个位置,选其中的4个位置用来放小棒,剩下的10个位置放巧克力,其可能性就是这个问题的答案了。因此,这两个不同的视角其实就是同一回事。

例2:Wynne老师手里有10块巧克力,要分给五位小朋友,要求每位小朋友至少分到一块巧克力,请问有多少种分法?

与例1相比,这里多了一个条件,就是要保证“每位小朋友至少分到一块巧克力”。要满足这个条件,我们可以先给五位小朋友每人一块巧克力,然后这个问题就转变为5位小朋友分5块巧克力的问题了。

巧用隔板法解答组合数学问题

因此,根据上一个问题,我们很快可以得到答案C(9,4)=126种分法。

例3:同时抛掷3个标准的六面骰子,将3个骰子面朝上的点数相加,其和为7的可能性有多少种?

巧用隔板法解答组合数学问题

这个问题本质上就是求不定方程x+y+z=7有多少组正整数解。因此,我们可以把不定方程中的两个“+”看成是“|”,插入7个点数之间的空档中,从而得到最终的答案。注意,这里与前两个例题不同的是,这里的隔板只能插在中间,不能出现在两头,因为点数不可能是0。

巧用隔板法解答组合数学问题

7个点数,有6个空档,选2个放“|”,即C(6,2)=15种可能性。

例4:有四个正的奇数相加,其和等于98。求满足条件的奇数组(x1,x2,x2,x4)有多少种可能性?

考虑奇数都可以表示为xi=2ki+1的形式,于是有:

98=x1+x2+x2+x4=(2k1+1)+(2k2+1)+(2k3+1)+(2k4+1) =2(k1+k2+k3+k4)+4。

因此,这个问题可以转化为k1+k2+k3+k4=47的不定方程问题了。用我们本讲的隔板法,很容易得到答案C(50,3)=19600。

例5:每次从1到9中选一个数字,选四次,若不考虑顺序,有多少种可能的组合?

巧用隔板法解答组合数学问题

这个问题很多人第一感觉会认为是9个数字里面选4个数字,所以是C(9,4)。对吗?当然不对。因为C(9,4)的数学含义是选出来的4个数字不能重复,但这道题目中,这4个数字是可以重复出现的,所以这个直觉是错误的。

还有人认为,是9的4次方。对吗?也不对。因为这里没有顺序问题。比如说,我第一次依次选出来的四个数字分别是1、2、2、3,第二次依次选出来的四个数字分别是2、1、3、2,第三次依次选出来的四个数字分别是3、2、1、2。因为题目要求是不考虑顺序问题,所以这三种情况其实是一种情况。因此,9的4次方是太大了,包含了太多重复的可能性。

因此,这个问题的答案最终将会介于C(9,4)和94之间。但这么说其实没有多少实际意义,因为这两个数之间的差距实在太大了。下面,我们通过三个不同的方法来解决这个问题。

解法一:分类讨论。如果用字母代替数字,在所有的可能性里,大致可以分为ABCD、AABC、AABB、AAAB、AAAA这五种大类。于是,

(1)ABCD:C(9,4)=126;

(2)AABC:C(9,3)×C(3,1)=84×3=252,这里的C(3,1)是因为从9个数字里选出来的3个数字,每一个都有可能成为其中的AA重复项;

(3)AABB:C(9,2)=36;

(4)AAAB:C(9,2)×C(2,1)=36×2=72,这里的C(2,1)是因为从9个数字里选出来的2个数字,任何一个都有可能成为其中的AAA重复项;

(5)AAAA:C(9,1)=9。

综上,全部的可能性为126+252+36+72+9=495种。

解法二:先看一个表格,表格中红色的数字代表1~9这9个数被选择的次数。我随便枚举了可能出现的几种情况,观察并寻找规律。

巧用隔板法解答组合数学问题

我们发现,无论哪种情况,9个数字被选择的次数之和总是等于4。这个结论看起来非常地显而易见。

然后,我把表格中红色数字用小圆点来表示,去掉其他的数字0,用小棒作为隔板将其分隔,继续观察规律。

巧用隔板法解答组合数学问题

于是,我们发现,1~9这9个数字,产生了8个间隔。因此,这个问题就转化为4个小球(1~9这9个数字被选择的总次数)如何放到这9个位置上去的问题,并且每个位置上的小球数在0~4之间。进一步地,这个问题就转化为4个小球和8个隔板如何排列顺序的问题。4个小球和8个隔板一共12个物品全排列,12!种可能性;因为4个小球和8个隔板都是同质的,会分别产生4!和8!种重复,我们要将其剔除;所以最后的结果就是12!/(4!×8!)=495种可能性。

这个结果其实相当于是在12个位置上选4个位置放4个小球,剩下的8个位置放8个隔板;或者说是,在12个位置上选8个位置放8个小球,剩下的4个位置放4个小球。于是,也可以表示为C(12,4)或C(12,8)。

这个问题可以一般化为k种物品选择r次,允许重复选择,其全部的可能性为C(r+k-1,r)。这个算法在数学竞赛中频繁出现,是一个重要的算法,在组合数学里叫做“多重集合的组合”问题。

例6:(AIME 2008)有两根不同的旗杆和19面旗帜,其中10面完全相同的蓝旗,9面完全相同的绿旗。现在要将所有的旗帜都挂到这两根旗杆上,使得每根旗杆上至少有一面旗帜,并且任意两面绿旗都互不相邻。设不同的排列数目为N,求N除以1000后的余数。

解法1:

为了说明方便,先给两根旗杆标为1号旗杆和2号旗杆。设Gn表示在1号旗杆上有n面绿旗的排列数。

假如其中一根旗杆挂上了所有的绿旗,为了保证任意两面绿旗都互不相邻,则这根旗杆上将至少挂8面蓝旗以作为任意两面绿旗的间隔;根据题意,我们还要确保2号旗杆上至少挂一面蓝旗;那么,最后剩下的一面蓝旗可以挂在10+1=11个位置上。于是我们可以得到:G0G9=11。

同理可以推出,假如当0<n<9时,则1号旗杆上挂有n面绿旗,同时至少还要确保n-1面蓝旗来进行间隔;相应地,2号旗杆上就挂有9-n面绿旗,同时至少有8-n面蓝旗。这里需要展开一下:当n=1时,1号旗杆上挂有1面绿旗,2号旗杆上会有8面绿旗;当n=2时,1号旗杆上挂有2面绿旗,2号旗杆上会有7面绿旗;n=3时,1号旗杆上挂有3面绿旗,2号旗杆上会有5面绿旗;……。无论n如何变化,我们都可以确定有7面蓝旗是被绿旗锁定了。那么,剩下的蓝旗就可以在(n+1)+(10-n)=11个位置中任意选择并可重复。于是,这个问题就相当于是从13个位置中选3个,因此剩下的3面蓝旗可能的排列数就是C(13,3)。

稍作停顿,说明一下,这里我估计有一些读者可能会理解不了。是的,没有打错,不是11,是13;因为11个位置中都可以重复放入剩余3面蓝旗中的任意一面,所以是用10个隔板将3面蓝旗相隔开来。

因而,全部的排列数为:2×11+8×C(13,3)=2310;最后的答案就是310。

解法2:

假如现在不是两根旗杆,而是一根旗杆,那么10面蓝旗和9面绿旗挂在这根旗杆上,如何才能保证任意两面绿旗都互不相邻呢?这个问题就相当于是要在10面蓝旗所构成的11个空位上选9个位置放绿旗的问题了。

然后,我们把这根旗杆一分为二,变成两根旗杆,就是我们题目所描述的情况了。但这里似乎忽视了一种情况,即第一根旗杆可能会以绿旗结束,同时第二根旗杆可能会以绿旗开始。这种情况符合题意,但在一根旗杆上是不被允许的。为了解决这个困扰,我们可以额外增加一面蓝旗作为分隔。因此,前面一根旗杆的情况就变为了在11面蓝旗所构成的12个空位上选9个位置放绿旗的问题了,即C(12,9)。又因为这11面蓝旗都可以作为两根旗杆一分为二的间隔,所以总共有11×C(12,9)=2420种排列方式。

但是,上面的计算中其实还包含了极端情况,就是所有的旗帜都在一根旗杆上的情况。由于两根旗杆是不同的,所以不符合题意的情况有2×C(11,9)=110种。

因此,综合起来就是N=11×C(12,9)-2×C(11,9)=2420-110=2310种。

解法3:

这种解法源自一位读者朋友提出,是在解法2的基础上进行变化思考。这个解法的要点是这里不用额外的蓝旗去作为分隔,考虑让蓝旗和绿旗排成一行,中间任选一个位置分成两部分,分别挂到2根旗杆上。为了满足题目要求,可以分2种情况讨论:情况1,9面绿旗之间都有蓝旗分隔;情况2,只存在2面绿旗相邻,但恰好从这2面绿旗之间进行分割,分别挂到不同的旗杆上去。

对于情况1,9面绿旗锁定8面蓝旗,剩余2面蓝旗,9面绿旗看作9个隔板,问题就转换为9个隔板分隔2面蓝旗,共C(11,2)种。此时19个旗子排成一行,为保证每个旗杆至少有一个旗子,旗子之间可以划分旗杆的位置还剩18个,这种情况的总数是18×C(11,2)=990。

对于情况2,可以将相邻的2面绿旗看作一个整体,视作一面“虚拟的”绿旗,例如12、23、34等,那么共有8种产生虚拟绿旗方案。此时问题就转换为对10面蓝旗和8面绿旗(其中1面为虚拟绿旗)进行排列,确保绿旗之间互不相邻。8面绿旗锁定7面蓝旗,剩余3面蓝旗,问题等价于8个隔板分隔3面蓝旗,共C(11,3)种。从虚拟绿旗中间放置旗杆。此情况数量是8×C(11,3)=1320。

综上两种情况,符合题意的排列总数是990+1320=2310。

解法4:

考虑两种情况:

情况1,两根旗杆上都挂有蓝旗。这个时候1号旗杆的蓝旗数量是从1~9,相对应地,2号旗杆的蓝旗数量就从9~1。在这9种情况下,任何一种情况都有12位置可供绿旗插入,所以相当于12个位置选9个位置放绿旗,即9×C(12,9)=1980种排列方法。

情况2,其中一根旗杆上没有蓝旗。这个时候,这根旗杆必须要一面绿旗以保证符合题意。那么,剩下的8面绿旗就可以插入11个空位上,即C(11,8);由于两根旗杆可以互换,所以全部的可能性是2×C(11,8)=330种。

因此,综合起来就是:9×C(12,9)+2×C(11,8)=1980+330=2310种。

上一篇:

下一篇:

相关阅读

分享