从 x + y = 5 的非负整数解，到如何解题？

这篇文章不能帮助你彻底的理解组合数学，但它尝试引领你在思考高维度问题做出一些不错的解决问题的方式。

直觉告诉我们的解决方式

我们从一个基本的问题开始：求 x + y = 5 的非负整数解个数?

很自然我们知道会有 6 组解，暂且可以枚举出来：

x = 0, y = 5;
x = 1, y = 4;
x = 2, y = 3;
x = 3, y = 2;
x = 4, y = 1;
x = 5, y = 0;

在我们完成这一道基本的问题后，我们的一个基本的解决问题的方式就已经逐渐浮出水面：分类讨论。

实际上，在我们解决问题时，会大量使用到这个基本的思维方式，这背后的底层逻辑就是：用分类来进行降维。因此分类讨论并非一种万能的解决方案，一旦分类讨论所需要的枚举条件过多，我们分类的复杂度就会线性增长。

不信，我们来尝试一下这个问题：求 x + y + z = 5 的非负整数解个数？

…

也许这个问题的答案是 21 。也许我们还能枚举出来，这里的篇幅就难以接受了。

从非负整数解到选位置的转变

暂且先考虑另一个问题：在并排序号为 1 - 7 的七个座位中，任意选中两个座位一共有几种选择方式？

我们运用基本的组合乘法原则，选中第一个有 7 种选择，此后选中第二有 6 中选择，但此时每个选择都重复计算一次。因此结果会是 21 个。运用组合数学的表达方式就是 C(7,2) = 21。

不难看出，在选择完座位之后，剩余的作为正好被分割成三个集合：【第一个座位之前 | 第一个座位和第二个座位之间，第二个座位之后】。当然这里每一部分也可以是空集。

值得兴奋的是，这种状况还能和 x + y + z = 5 形成一种默契的一一映射。（显然剩下的三个集合一共有五个座位）

以上是一个简单的抽象，把非负整数解的个数映射为组合的个数。这就是我们使用的另一种思考方式：等价转换。

过去的时间里，我们可能大量地把这种方法用在证明题的解答中，在这里自然能看出这种等价转换的威力。

当然，如果足够细心可以发现 6 和 21 这两个数有不解之缘。

让我们把问题的难度加大：四元方程 w + x + y + z = 5 的非负整数解个数？

面对四元方程，很自然也可以按照刚才的组合数据得到 C(8,3)

按照分类讨论的想法，我们同样也会得到解的个数为：

W = 0 ，x + y + z = 5，此时有 C(7, 2) 个解；
W = 1 ，x + y + z = 4，此时有 C(6, 2) 个解；
W = 2 ，x + y + z = 3，此时有 C(5, 2) 个解；
W = 3 ，x + y + z = 2，此时有 C(4, 2) 个解；
W = 4 ，x + y + z = 1，此时有 C(3 2) 个解；
W = 5 ，x + y + z = 0，此时有 C(2, 2) 个解；

总计 C(7,2) + C(6,2) + C(5,2) + C(4,2) + C(3,2) + C(2,2) = C(8,3) ，这正是组合数学的公式之一。到这一步，我们的结论正好与组合数学的原理十分符合，起码我们的等价转换并不存在矛盾的解释。

在进行下一个问题之前，也许有一个笑话值得品一品：

一天，数学家觉得自己已受够了数学，于是他跑到消防队去宣布他想当消防员。
消防队长说：「您看上去不错，可是我得先给您一个测试。」
消防队长带数学家到消防队后院小巷，巷子里有一个货栈，一只消防栓和一卷软管。
消防队长问：「假设货栈起火，您怎么办？」
数学家回答：「我把消防栓接到软管上，打开水龙，把火浇灭。」
消防队长说：「完全正确。最后一个问题：假设您走进小巷，而货栈没有起火，您怎么办？」
数学家疑惑地思索了半天，终于答道：「我就把货栈点着。」
消防队长大叫起来：「什么？太可怕了，您为什么要把货栈点着？」
数学家回答：「这样我就把问题化简为一个我已经解决过的问题了。」

这里就是我们的又一种武器：归约化简。

如果把我们的约束条件等式换成不等式，情况又会有什么不同呢：x + y + z <= 5。

我很合乎逻辑的一种解法就是分类讨论，针对 x + y + z 的值讨论，转化为 x + y + z = N（常数）这个已知的问题，我们的问题自然就迎刃而解。

按照分类讨论：x + y + z = 5，4，3，2，1，0。

x + y + z = 5，此时有 C(7, 2) 个解；
x + y + z = 4，此时有 C(6, 2) 个解；
x + y + z = 3，此时有 C(5, 2) 个解；
x + y + z = 2，此时有 C(4, 2) 个解；
x + y + z = 1，此时有 C(3 2) 个解；
x + y + z = 0，此时有 C(2, 2) 个解；

总计 C(7,2) + C(6,2) + C(5,2) + C(4,2) + C(3,2) + C(2,2) = C(8, 3) 个

尽管我们确实得到的 x + y + z <= 5 的解答，看到 C(8,3) 这个解答总是不免让人气恼。我们对 w + x + y + z = 5 的答案也是它。能不能一步到位的找到 C(8，3)。

x + y + z <= 5 和 w + x + y + z = 5 是可以形成一一映射的：

对于每一个 w ，若 0 <= w <= 5，总存在一组（x, y, z）满足 x + y + z <= 5；
总每一组（x, y, z），若 0 <= x + y + z <= 5，总能引入非负整数 w 满足 x + y + z = 5；

这样一来就可以把两个不同维的问题形成对应。尽管从某种程度上，二者的维度的复杂度是仍然是完全一致的，但我们达成了降低计算复杂度的目的。

看上去，这里我们仍然是在使用归约化简的想法，但是读者应该也能感觉到的不和谐之处在于：

这里的解法其实并不那么显然，这里凭空多出来的 "w" 正像是反证法中的“不妨考虑”无比罪恶。

是的，但看数学证明就是如此单调，似乎所有的思考空间都会被这种“取巧”的想象力扼杀。问题泛化就是一种大胆的策略，没有这种大胆的尝试，很难有“初极狭，才通人，复行数十步，豁然开朗”的体验。对于某些问题，求解泛化的问题也许会比求解原问题容易得多。

留给读者思考：

非负整数 x + y + z < 5 的非负整数解的个数
正整数 a + b +c < 5 的非负整数解的个数

shotcut：

x + y + z < 5 和 x + y + z <= 4 能否建立映射呢？
正整数 a + b +c < 5 和 x + y + z < 8 能否建立映射呢？

DaftKen 小站

搜索此博客