一一对应

组合数学 数学

概念

一一对应是计数时常用的一种技巧, 若性质 $A$ 的计数较为困难, 性质 $B$ 的计数比较容易, 但性质 $A$ 和 性质 $B$ 一一对应, 则对性质 $A$ 的计数可转换为对性质 $B$ 的计数.

我感觉这所谓的"一一对应"和平常做题中会用到的"正难则反"有异曲同工之妙, 都是逆向思维的运用.

书上有一个特别有意思的例子,

有 100 名乒乓球选手通过淘汰赛, 最后产生一名冠军, 问有一共需要进行多少场比赛?

先按照一般思维来想, 100 名选手, 先两两比赛, 就有 50 场,
50 名选手, 再两两比赛, 又有 25 场,
25 名选手, 那就需要让一位选手直接晋级, 剩下的人进行 12 场比赛,
13 名选手, 一人直接晋级, 6 场比赛,
7 名选手, 一人晋级, 3 场比赛,
4 名选手, 2 场比赛,
2 名选手, 1 场比赛, 产生冠军.

那么一共就有 50+25+12+6+3+2+1=99 场比赛.
算是算出来了, 就是有点麻烦, 万一是 1000名, 10000000名选手, 那么直接模拟就不太可能了.

其实我们稍微换一下角度, 就可以发现, 既然是淘汰赛, 最后要产生一名冠军, 那么就要淘汰 99 名选手, 每场比赛淘汰 1 名选手, 那不就是 99 场比赛吗?

当初看这道题的时候感觉自己就是个sb...

Cayley 定理

Cayley 定理 : 过 $n$ 个有标志顶点的树的数目等于 $n^{n-2}$.
理解:
现在有一棵固定了形态的树, 我们按照一下规则将这棵树转换成一个序列,

每次删掉树中 度为 1 且标号最小的节点, 并将这个节点相邻的节点加入序列中, 直到树中只剩一条边为止.

举个例子, 我们给出一个这样的树 (luogu图床死活加载不出来, 你们手动画一下吧...)

1 2
1 3
1 6
1 8
2 5
2 7
4 7

删掉 3, 把 1 加入序列中,
删掉 4, 把 7 加入序列中,
删掉 5, 把 2 加入序列中,
删掉 6, 把 1 加入序列中,
删掉 7, 把 2 加入序列中,
删掉 2, 把 1 加入序列中.

最后, 我们就得到了一个长度为 $n-2$ 的序列 : 172121.

显然, 当一棵树的节点个数为 $n$ 时, 就有 $n^{n-2}$ 个不同的序列,
我们若能证明每一个序列都对应着一颗树, 即序列和树一一对应, 就可以证明该定理.

我们考虑一下, 决定一棵树的形态的因素其实就 2 点 :

1. 每个节点的度.
2. 每个节点所连接的节点.

我们观察一下这个序列, 很容易发现, 这个序列中, 每个节点编号的出现次数加上 1 就是这个节点在树中的度.
这是因为每个节点在它的相邻节点被删去时, 它都会被加入序列中, 那么再加上它自己被删除的那一次, 就是这个节点的度了.

那么, 我们可以根据上面那个序列来列一个表

我们看看要如何根据这个序列来复原它所对应的树. (172121)

首先, 因为我们是每次删除度为 1 且编号最小的节点, 那我们就从编号最小的开始从上往下看.

首先是 3 , 相对应的, 序列中第一个数是 1 , 那么 3 和 1 之间肯定有一条边.
接着是 4 , 同理, 4 和 7 之间也一定有一条边.

像这样, 我们将原来构造序列的规则反过来, 就可以把这个序列还原为它所对应的树, 所以每个序列和树都是一一对应的, 那么这个定理就不难理解了.