排列组合——淘汰赛——格子模型

castelu · 发表于 2008-4-15 17:57:46

例题：
中韩围棋擂台赛每方出八名棋手进行比赛，规则规定：每方先出一名选手进行比赛，胜者继续参赛，负者被淘汰，依此进行，直到一方选手全部被淘汰，则比赛结束。
求一共可能出现多少种比赛的结果？

解答：
这种比赛类似于“车轮战”，直接分析比较困难，因此引入一种格子模型。
如图：
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
先画出16个格子，然后分别将两队队员放入
规定：格子右边的人总是把左边的人给打败，本队的人不打自己的队员
示例：
以1-8表示中方队员，以a-h表示韩方队员
其中一种任意放法是：
1 a 2 b c 3 d 4 e f g 5 6 7 8 h

这种排放情况等同于一种比赛结果，即：
a打败1
2打败a
b打败2
3打败b c
d打败3
4打败d
e打败4
5打败e f g
h打败5 6 7 8

因此，有几种排放方法就等于有几种比赛结果
问题转化
显然，只要从16个位置中选出8个位置给中方队员即可

答案为：C₁₆⁸