排列组合为什么这么难

自从开学起，我已经与排列组合折腾了好几个月了。在此过程中，我也一直在反复思考、追问一个问题：「排列组合为什么这么难？」然而直到今天，我也只有了一些模糊的思路而已。故记录如下。

首先，我们先要搞清楚的是「排列组合难在哪里？」我认为最困扰我的一点是：有太多的「做题技巧」，而其中绝大多数的适用范围都是不明确的。也就是说，当看到一个问题时，我会想到很多个可能的解决方法，却又感觉哪一个都不像。

我现在想试着解释一下，为什么会出现这样的情况。首先我们来看最简单的一道题：有五个数\(\begin{Bmatrix} a, b, c, d, e \end{Bmatrix}\)，现在从前三个数（注意必须是前三个数）中同时任意取出两个数，求有多少种可能的情况？如果你学过排列组合或者看过我之前写的《排列组合笔记》，很容易看出答案是\(C^{2}_{3}\)，也即「3个里面取2个，不关心顺序」。 \[ \begin{aligned} C^{2}_{3}&=\dfrac {3!}{2!\left( 3-2\right) !}\\ &=\dfrac {3\times 2}{2\times 1}\\ &=3 \end{aligned} \] 但是这里有一点可能会引起你的注意：\(C^{2}_{3}\)中的3为什么一定是那前三个数？如果不是，那岂不是不符合题目条件了吗？然而稍微思考一下，又会发现无论是取前三个还是后三个，又或者是中间三个等等，得到的结果都应该是一样的。这又意味着什么呢？我想把这样的现象概括为：「问题空间」和「解空间」的元素，不满足一一对应的关系，而是多对一的关系。「问题空间」代表的自然就是纯粹的题目存在的空间。「解空间」代表的就是\(C^{2}_{3}\)，或者简单地说成是3这个数字（显然这两者是等价的，数学运算只是一种等价变换而已）存在的空间。

这种多对一的关系又意味着什么呢？首先，它包含着一种抽象。实际上，原本的问题与最终的答案\(C^{2}_{3}\)比起来，所包含的信息量是降低了，然而\(C^{2}_{3}\)与3比起来没有任何差别——我们可以把它们看成表达「3个里面取2个，不关心顺序」的个数的两个记号。我们解题的过程，就是抛弃对最终结果没有影响的信息，从而简化问题，最终映射到已经抽象好的模型的过程。当然，这只是这一道题的情况。有的题目需要你想办法排除妨碍你简化问题的信息，比如定序排列（排列问题，不过需要你让某几个被排列的东西按一定的顺序出现）就需要利用除法把不符合要求的情况排除掉。从排列数公式推出组合数公式就是这种问题。不过很有意思的是，这个基于除法的定序方法同样也是多对一的情况：你不能「保证」你定序的就是题目要求的那几个东西，不过你可以保证的是，无论定序的是哪几个，除数都是一样的。也就是说，「简化问题」本身也可以当作问题去看，并且也有它自己的模型。

我们当然不是第一次接触这样的抽象了。早在小学的时候，我们就知道无论是苹果的个数、施工天数还是跑步的距离都可以看作\(x,y\)等字母，然后列出方程，解出答案。不过这种抽象比较简单，因为这差不多是一种一一对应的关系：把个数、时间、距离等一一替换成\(x,y\)等字母是让人觉得可靠的，甚至我们都感觉不到丢失了信息。然而在排列组合问题里情况就复杂得多了：你很难确定哪一些信息不会对结果产生影响。

以往我在解题的时候，思维都是一条单行线：先看题目有哪些条件，然后逐个考虑解决方法，最后连起来得到解法。但是现在看来，这样做常常是行不通的。我更应该考虑的是「我可以从什么方面简化、抽象问题？」