在解决组合计数问题中，我们经常会用到一种技巧，叫做“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个位置上。于是我们可以得到：G0＝G9＝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种。