[快乐数学]组合数学 卡特兰数与W线

好久没更新了啊。给兄弟们整个新活。今儿探讨的问题是关于排列组合的。(别问我为啥现在才更新，蟹蟹)

1.引例

直接上干货了。

这是一个较为复杂的计数问题。 你或许没看懂。我简单解释一下题目。 假设道路左侧有三辆车编号为a,b,c。 这三辆车必须先开进检查站然后从右侧离开。 (检查站里可以停无数辆车) 假如a先进检查站然后出站。 然后b进检查站，c跟着进检查站。 此时b被c挡住了，因此只能c先出站然后b再出站。 那么三辆车出站的顺序就是a,c,b了。 这题就是要计算总共有几种可能的出站顺序。 为了不让你直接空手枚举出答案，题目假定一开始有161616辆车。我倒觉得不如直接变成n辆车。

2.特点概括

咱们先对这一类问题做一个特点概括。 这类问题的关键点是那个检查站。

1.

所有元素必须先进入检查站然后离开检查站。

2.

检查站只允许最后一个进站的车离开即

先进后出

。

熟悉计算机科学的应该会知道，这恰好是计算机科学中

栈

这个数据结构的特点。

好吧，那我简单科普一下，毕竟这玩意生活中很常见。 比如说咱们洗碗，每洗一个碗就把它叠到已经洗好的碗堆上。这样的一叠碗，如果你要拿出其中的一只碗是不是只能从顶上拿。如果你不动整叠碗，那你想放新碗也只能在顶上放。所有的碗将来也都要放到那个碗堆里吧。 在计算机科学里，如果我们要模拟这堆碗的情况，是不是也就需要类似的结构了。 因此，计算机科学中定义了一类专门的数据结构称为栈也具有类似的特性。 碗堆有两头，一头可以放和拿新碗，对应栈顶(top)。 另一头不可以，对应栈底(bottom)。 放新碗称作压栈(push)。 把碗拿走称为出栈(pop)。 只能对最上面的碗进行操作对应只能对栈顶数据操作。 先放的碗反而要后拿就是先进后出了。

3.图解

好了，回归正题。毕竟你们是来看这类问题怎么解的而不是来看什么栈的。 这类问题我们是可以利用一张图来解决的。(这种离散问题的图解你是不是在数列里看到过呢？蛛网图对吧) 我们用横坐标x表示曾经或正在站内的车的数量。 用纵坐标y表示已经出站的车的数量。 那么一开始所有车都没进出站，因此对应(0，0)点。 最后所有车都进站然后出站了，对应(n，n)点。 每次我们的操作都是让一辆车进站或者出站。也就是让横坐标或者纵坐标+1。 因此总的实现路径就是一条沿着格点从(0，0)到(n，n)的折线。 比如这样，

然而，有一条红线不能碰。 如果检查站里已经没有车了那么我们就不能继续执行让一辆车离开的操作了。 这样的路径是

非法

的。 那，哪些路径是非法的呢？ 咱们往前迈一步。 让没有车的检查站继续出车的前一步是不是检查站没有车啊。 那检查站没有车的时候，横纵坐标是不是相等的啊。 因此，临界线就是y=x。 越过y=x的路径就是非法路径。或者说，我们要时刻保持y≤x。 额，你还没想明白吗？ 那就正着想。 每次出车前需要先保证检查站有车。 那么曾经和现在入站的车的数目x 就必须大于等于 已经出站的车的数目y。 也就是x≥y。 那么非法路径就经过了y=x上方的区域。 或者说非法路径触碰了y=x+1这条线。 如果我们排除了所有非法路径那就能计算出合法路径的数目了。 当然，前提是我们要先算出所有路径(包括合法与非法的) 这个非常简单。 从(0，0)到(n，n)总共需要走2n步，其中你需要选择n步往右，剩余的n步自然就是往左了。 因此总的方法数的C(2n n) 接着只要算出所有非法的路径的个数即可。 这个其实也很简单。 非法路径走的时候必然遇到y=x+1这条线，这时我们做前一部分路径关于y=x的的对称路径。 得到一条从(-1，1)到(n，n)的路径。 这条路径的总个数和非法路径的总个数是相等的。(证明就交给你喽，之后我会稍微给你个提示) 从(-1，1)到(n，n)总共需要(n-(-1))+(n-1)=2n步，其中n+1步向左，n-1步向上。 因此路径总数为C(2n n-1)。 二者相减就是本专栏探讨的问题的解答了。

4.杂谈

在本专栏的第三部分我们用图解的方式解决了这个问题。实际上，这张图被称作惠特沃斯（Whitworth）线。 而问题的答案C(2n n)-C(2n n-1)被称作卡特兰数。 不过你看到的卡特兰数公式应该不是这样的。 利用组合数公式 C(2n n)-C(2n n-1)=C(2n,n)/(n+1) (n=0,1,2,...) 后者是更常见的卡特兰数公式。 至于前面提到的提示嘛。 既然是提示我就不能说得太明显了，给你大致指个方向。 你想想，怎么证明两个集合所含元素数相等？ 最简单的办法当然是把两个集合所含元素个数数出来比较喽。 但我们就是为了求元素个数，因此不能用这个方法。 想一想，如果你拿了一箱苹果要分给班里的同学们，你怎么在不数你带了几个苹果的情况下知道同学多还是苹果多呢？ 直接分一分呗。 给每个同学一个苹果，如果每个同学都分到了一个而且没有多余的苹果(这一半你也可以认为是在给苹果找主人，每个苹果都有一个主人)就说明苹果和同学数目一样。 如果我们抽象到纯数学领域上就是建立苹果和同学的映射关系满足， 每个苹果都有唯一确定的同学与之对应。(构成苹果到同学的映射f) 每一个同学都有至少一个苹果(f是满射) 不同的苹果有不同的主人。(f是单射) 如果一个映射既是单射又是满射，那么这个映射就是双射。 因此要比较两个集合所含元素的多少可以通过建立映射关系来实现。 一般地，如果我们能建立集合A到集合B的双射f，那么集合A与集合B所含元素的个数相等。 特殊地，这条对含有无穷多个元素的集合也成立。(这个涉及到实变了，我就不多展开了。有兴趣的话可以自己去网上查阅资料)