换个角度思考,看穿问题本质

淘汰赛
先从一个简单的例子入手,现在有16个人打淘汰赛,淘汰赛即一次决胜负,可以有轮空,问:一共要打多少场比赛才能决出冠军?
答案是15次,计算过程很简单:1+2^2+2^3=2^4-1=16-1=15
同理可得32个人为2^5-1=32-1=31次,64人为64-1=63次。
从上面的例子你能否大胆地说,当人数为n时,需要的比赛次数为n-1?比如236人淘汰赛需要235场比赛。可能你会迟疑,因为在前三个例子推导时用到了等比公式,但是换一个角度来思考,每一个被淘汰的人一定会经历一次他自己失败的比赛,这样就形成了选手和比赛的一一对应,也就是说n个人必须要n-1场比赛才能淘汰出冠军,这么一想就豁然开朗了。
Cayley定理
接下来这个例子略微复杂,不过因为必考并且同样非常有趣就记录于此。
问题是这样的:给定n个不同的点,一共有多少个由这n个点的生成树?
简单解释一下什么叫树,树就是一种无孤点无环的连接,生成树就是把每一个点都看成不同的点,下面是n=2、3、4时的所有生成树构造。

咋一想或许毫无思路,但答案却出奇得简洁:一共有n^(n-2)种。
证明的思路非常巧妙,关键就在于如何构造出每一种树和序列的一一对应,下面会用一个具体的例子来解释证明思路。(语言未必严谨)
由于每个点视作不一样,我们从1开始对每个点赋值,然后依次执行下面的步骤直到只剩下两个点:
1.删去最小的叶子节点。
2.记录下来与删去叶子节点相连的节点的数。
具体步骤如下:

这样我们就得到了一个和树相对应的(n-2)元序列,这个序列是一一对应一种树,然后再应用乘法原理,每个位置可以填n个数,就很容易得出以上结论。
下面展示一下如何通过序列还原一棵树,思路也很简单,先排除序列中出现的数,然后看剩下的数还有哪些,然后一步一步填上去即可,一个具体的例子如下:

p.s. 组合数学是我大三以来上的最开心的一门课,上课过程中不断“aha”、“妙啊”,真的给我一种完全不同的思考问题的角度,期待下面的课程。