问题：
12个高矮不同的人，排成两排，每排6个人，每一排都从矮到高排列，且第二排都比对应的第一排的人要高，问共有多少种不同的排列方式？，如果一共有n(n为偶数)个人，一共有多少种排列方式？
解释：
这道题是一道隐藏很深的卡特兰数问题。
排列的形式如图所示，每排身高递增，同时第二排比对应第一排要高。
首先将12个人按照身高递增排序，这个排序是唯一的。我们要做的是在这个已经排序好的序列中挑出6个放在第一排，剩余6个放在第二排，且必须满足题目所叙述条件。我们把12人中排在第一排的人设为 -1 ，将排在第二排的人设为 1，那么我们要找的的就是符合条件的-1，1序列的个数。把从左到右遇到的第一个-1放到第一排的最左面，把从左到右遇到的第二个-1放到第一排的左二位置，依此类推。同理，我们把从左到右遇到的第一个1放到第二排的最左面，把从左到右遇到的第二个1放到第二排的左二位置，依此类推。如图给出了一种符合条件的置-1，1的方式，棕色表示1，浅绿表示-1.
序列是： -1 1 -1 1 -1 1 -1 1 -1 1 -1 1
或者这样
序列是：-1 -1 -1 -1 -1 -1 1 1 1 1 1 1
我们要做的就是如何找出合适的-1，1序列。
仔细思考就会发现：
如果 设序列为： a1 a2 ….. a12, 那么 只有对于任意k （k<=12） 满足a1+a2+…+ak <=0 的序列才是合法的，如果出现a1+a2+…+ak > 0 序列，一定不是合法的，这种情况如下图：
这种情况序列是：
-1 1 1 -1 -1 -1 1 -1 -1 1 1 1，当k = 3的时候，a1+a2+a3>0,这种情况就是违法的，原因示图如下：
在这种情况下就会出现第二排比第一排要低的情况，所以就是违法的。
同样的情况，从左到右的-1，1序列中的1的个数任何时候都不能比-1 的个数多，否则就是违法的。所以这道题就转化成如下问题： 6组（-1，1）对 进行排列，并且 从左到右遍历，1的个数不能比-1多，这就是一个典型的卡特兰数问题。
-1 1 序列的总个数是：a = c(2n,n) ，这道题中 n = 6
-1 1 序列中违法的序列总个数是：b = c(2n,n+1)
符合条件的序列数就是： c = a – b = c(2n,n) /(n+1) ,结果 c 就是卡特兰数的通式。
对于 a 和 b 的解释：
a = c(2n,n) :
有12个数字，6个-1，6个1，我们只要在12个空格中随机挑选6个放1，剩下的就自然放-1，所以就是c(12,6)。
b = c(2n,n+1) :
对于任何一个违法序列，比如：
-1 1 1 -1 -1 -1 1 -1 -1 1 1 1 , 从第三位开始1的个数比-1多，将前三位全部取反，其余不变：
1 -1 -1 -1 -1 -1 1 -1 -1 1 1 1
那么 -1 的个数就变成了 7，1的个数就变为了 5，仔细思考可以发现对于任何违法序列在进行如上操作后，-1的个数都会变为n+1，而1的个数都会变为n-1，实际上任何一个由 n+1 个-1，n-1个1构成的序列再进行逆反转形成后的 n个-1，n个1的序列都是违法序列，n+1个-1，n-1个1总共可以构成 c(2n,n+1)个序列，他们逆反转后全部是违法序列，互相的关系之间是一一对应的。
综上，总共的合法排序数目就是:
c(2n,n) /(n+1)
代码求解：
public static int countWays(int n) {n >>= 1;int res = 1;for (int i = 2 * n; i > n; i--) {res *= i;}for (int i = 1; i <= n + 1; i++) {res /= i;}return res;}
