隔板法与对应法

有人将计数问题“总结”成：若干个球放入若干个盒子问题，其中球可以是相同的（彼此之间不作区分），也可以是不同的；盒子可以是相同的，也可以是不同的；另外，每个盒子中球的数目可以没有限制，也可以有要求．于是就出来$8$种不同的计数问题模型，比如将四本不同的书送给三个人，要求每人至少一本．有多少种不同的分法？就是对应球不同，盒不同，盒中球数有要求的．今天我们想讲的是针对：球相同，盒不同的问题，从每盒至少一球开始，再延伸到球数的各种其它限制上，由此来讲讲隔板法与对应法．

大家比较熟悉的问题是把$10$个名额分配给$3$个班，要求每个班都至少得到一个名额，问有多少种分法？对于这类问题，可以用隔板法就可以，为了后面延伸起来方便，我们把这个问题表达成：

已知$x_1+x_2+x_3=10$，求此方程的正整数解$(x_1,x_2,x_3)$的个数？

解　我们想象$10$个相同的球放成一排，那么共有$9$个空隙产生，往这$9$个空隙中选择两个空隙放入两块隔板，就可以将这些球分成三堆，如下图，对应的解为$(3,2,5)$：

于是我们得到方程的解的个数为$\mathrm{C}_9^2=36$；

上面这种方法我们称为隔板法，对于这种盒子不空的排法，直接用隔板法就可以解决．如果对$x_i$的限制产生了变化，比如只要求$x_i\in\mathcal{N}$，那么直接用隔板法就无法解决了．这时我们的解决思路是，根据某种一一对应关系，把这个问题转化成可以用隔板法解决的问题．

例题一　（1）已知$x_1+x_2+x_3=10$，其中$x_i\in\mathcal{N},i=1,2,3$，求满足此条件的方程的解$(x_1,x_2,x_3)$的个数？

（2）已知$x_1+x_2+x_3=10$，其中$x_i\in\mathcal{N}$，且$x_i\geqslant i,i=1,2,3$，求满足此条件的方程的解$(x_1,x_2,x_3)$的个数？

分析与解　（1）记$$y_i=x_i+1,i=1,2,3,$$于是得到新的方程$$y_1+y_2+y_3=13,y_i\in\mathcal{N}^*,i=1,2,3.$$原方程的每一组解$(x_1,x_2,x_3)$与新的方程的每一组非负整数解$(y_1,y_2,y_3)$一一对应．比如$(3,0,7)$对应到$(4,1,8)$．由这样的对应关系，问题转化成求$y_1+y_2+y_3=13$的非负整数解的个数，由隔板法知解的个数为$\mathrm{C}_{12}^2=66$．

（2）记$$z_1=x_1,z_2=x_2-1,z_3=x_3-2,$$于是得到新的方程$$z_1+z_2+z_3=7,z_i\in\mathcal{N}^*.$$此方程的解的个数为$\mathrm{C}_6^2=15$，即为所求的解的个数．

注　用放球入盒的思路，对应法可以这么理解：对于（1），先往$10$个球中加入三个球，然后用隔板法正常分配这$13$个球，最后从每个盒中拿走一个球，这样有的盒子就可能是空的，满足了要求．对于（2），先往第二个盒中放入$1$个球，第三个盒中放入$2$个球，再对剩下的$7$个球用隔板法分配，这样分配完正好可以满足球数的要求．

---

例题二　求$(1+x+x^2+\cdots+x^{10})^3$的展开式中包含$x^{15}$的项的系数．

分析与解　一共是三个因式相乘，从每个因式中分别抽取一项$x^i,x^j,x^k,0\leqslant i,j,k\leqslant 10$相乘会给展开式中的项$x^{i+j+k}$的系数增加$1$，所以满足条件的解的个数就对应项的系数，即本题需要计算$$i+j+k=15,0\leqslant i,j,k\leqslant 10$$的解$(i,j,k)$的个数．

我们用排队法：先不考虑$i,j,i\leqslant 10$，我们可以由对应法和隔板法得到满足$i,j,k\geqslant 0$的解的个数为$\mathrm{C}_{17}^2=136$．

再考虑不满足的解的个数，形如$(11,2,2)$：

首先不满足的解$(i,j,k)$中，$i,j,k$有且只有一项超过$10$，先确定超过$10$的项，有$3$种可能；

再考虑$(i,j,k)$中$i\geqslant 11$的解的个数，我们考虑对应$$i'=i-10,j'=j+1,k'=k+1,$$则$i'+j'+k'=7$，且$i',j',k'$都为非负整数，故解的个数为$\mathrm{C}_6^2=15$．

所以$x^{15}$的系数为$$\mathrm{C}_{17}^2-3\mathrm{C}_6^2=136-45=91.$$

---

最后给出一道练习：

将$20$个名额分给$4$个班，

（1）要求每个班至少有三个名额，问一共有多少种不同的分法？

（2）要求每个班的名额数都是偶数（不为零），问一共有多少种不同的分法？

答案　（1）$\mathrm{C}_{11}^3=165$；

（2）$\mathrm{C}_{9}^3=84$．

对应法将一个我们不熟悉的问题通过一一对应的关系指向我们熟悉的问题，体现的是数学中的转化化归的思想．有一个经典的笑话讲数学家的这种化不熟悉为熟悉的能力．一天，有位数学家觉得自己已经受够了数学，于是跑到消防队去宣布他想当消防员．消防队长说我得先给您一个测试，他带着数学家到消防队后院小巷，巷子里有一个货栈，一只消防栓和一卷软管．消防队长问：“假如货栈起火，您怎么办？”数学家回答说：“我把消防栓接到软管上，打开不龙头，把火浇灭．”消防队长说：“完全正确！最后一个问题：假设您走进小巷，而货栈没有起火，您怎么办？”数学家不假思索地答道：“那我就把货栈点着，这样我就把问题化简为一个我已经解决过的问题了．”

更多相关问题见每日一题[372]双剑合璧．