首先满足奇数位递增这个条件

显然有且只有从\(2n\)个数中取\(n\)个数，即\(C_{2n}^{n}\)，就能满足这个条件

在满足这个条件之后，剩下了\(n\)个数，显然顺序不能变

举个例子\(n=3\)

那么假设取出了\(1\) \(2\) \(5\)

那么剩下三个数的顺序只能是\(3\) \(4\) \(6\)，不能是其他的如\(4\) \(6\) \(3\)或者\(6\) \(4\) \(3\)

所以现在就剩下最后一个条件需要满足

其实这里已经能看出来卡特兰数的影子了

将最开始取出的\(n\)个数变为\(1\)，剩下的数位\(0\)

显然在任意位置\(0\)的前缀和必须比\(1\)少（反证法证明）

另一方面在任意位置\(0\)的前缀和必须比\(1\)少的数列显然满足最后一个条件

所以是卡特兰数