问题:
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;
}