一、奇妙的组合

           ——关于排列的迷题

组合分析，即组合学，是研究事件如何排列的。用专业的说法，组合分析是将诸元素按不同的规则和特性组合为集合的研究方法。

例如，第一个问题是关于不同颜色的球的分组方法。这个问题要求读者按某一特性找到彩球的最小集合。第二个问题是关于参赛者按图表以淘汰制分组的方法——这也是计算机中重要的计算部分数据分类的问题。

组合分析通常要找到根据某种规则进行分组的全部组合，如所谓“穷举问题”在苏珊上学路径中的应用，在这个问题上，组合的元素是沿模型边缘的曲线路径，由于几何图形被引入，我们称其为组合几何。

每个数学分支都有其组合问题，你将在本书各节中找到它们。有组合数学，组合拓扑，组合逻辑，组合集合理论——甚至组合语言，这将在语词游戏一章看到。组合学在概率理论方面尤为重要，在找到概率公式以前列举所有可能的组合是非常必要的。有一个著名的概率问题集叫作“机会与机遇”，题目中“机会”这个词指的就是组合因素。

我们第一个问题涉及概率是因为彩球按某一特定要求排列，文中提出了如何解决类似的简单的概率问题。列举苏珊上学路径问题提供了帕斯卡三角在概率问题中的应用。解决已知组合问题的排列可能没有，可能只有一种，也可能有几种或无数种。没有一种两个奇数的组合能使这两个奇数的和仍是奇数。只有一种两个质数的组合，使得这两个质数的积是21，满足两个正整数的和是7的组合有三种，有无限多种两个偶数的组合使得它们的和仍是偶数。在组合理论中更多的是很难找到“不可能事件的证明”，即没有满足要求的组合。例如，直到最近才证明地图的绘制需要五种颜色，这在组合拓扑中曾是一个著名的无解问题，这个不可能证明需要庞杂的计算机程序。

另一方面，许多最初很难证明其不可能性的组合问题，在具有了巧妙的想法后却很容易证明。在“恼人的花砖”问题中，我们看到简单的奇偶检验马上导致了用其它方式很难证明的组合的不可能性。

关于小球的第二个问题把组合思想和不同数学体系的应用结合了起来。我们知道，可以依赖组合的规则，用数学做各个位置的记号，实际上，所有的推理，无论是数学的还是逻辑的，都能用一串组合符号来进行，不管这是不是合适的说法。

所以17世纪组合学的创始人莱布尼茨称这种推论技巧为排列组合。

上一页   下一页