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

castelu

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

解答：
这种比赛类似于“车轮战”，直接分析比较困难，因此引入一种格子模型。
如图：
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
先画出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₁₆⁸

castelu

原来如此，多谢指教

远知

这个格子模型的专业名称叫做“栈”，是计算机中常用的一种数据结构。它的本质是一个只可以从一侧进行添加的删除的数列。题目的模型可以认为是将两个栈进行归并操作成为一个栈，有几种可能的结果。其理论发展的已经很完善。

巫师无视

没必要这么做吧　　直接就出答案了

锟子

哇，真的很难想到，不错！

jwxxixihaha123

好，厉害，这也行

泡面

这个方法很好啊.....
多学学