当前位置: 代码迷 >> 综合 >> 卡特兰数(Catalan)证明及应用:12个高矮不同的人排成前后两队
  详细解决方案

卡特兰数(Catalan)证明及应用:12个高矮不同的人排成前后两队

热度:35   发布时间:2023-12-13 10:26:30.0

【概述】:
令h(0)=1,h(1)=1,catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2);

解为h(n) =这里写图片描述

unsigned long h(int n)//求卡特兰数
{if (n < 0){ cout << "wrong input!" <<endl;return EXIT_FAILURE;}unsigned long ret = 0;if (n == 0 || n == 1)return 1;for (int i = 0; i != n; ++i)ret += h(i)*h(n - i - 1);return ret;
}

【卡特兰数对应出栈次序问题】n个自然数1~n进栈(栈无穷大),任何一个数进栈的同时可以选择出栈,比如第一个数进栈完毕,下一个动作可以选择出栈或后一个数进栈,进栈次序为1、2、3……n,问不同的出栈次序有几种?
我们可以这样想,假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数,这k-1个数出栈一共有h(k-1)种方案(h是函数规则,这里函数规则是一样的,想想为什么?)。比k晚进栈且早出栈的有n-k个数,一共有h(n-k)种方案。所以一共有h(k-1)*h(n-k)种方案。显而易见,k取不同值时,产生的出栈序列是相互独立的,所以结果可以累加。k的取值范围为1至n,所以结果就为h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0)

【递推解的证明】:
【等价问题】:n个1和n个0组成一个2n位的2进制数,要求从左到右扫描,1的累计数不小于0的累计数,试求满足这条件的数有多少?

进栈看作1,出栈看作0,由于在任何时候进栈累计数都不会小于出栈累计数(否则没有元素进栈怎么会有元素出栈),所以这两个问题是等价的(仔细想一想)!根据上面的出栈次序问题,可以得到这样的数有h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0)个,满足递推式。

另一方面,在2n位上填入n个1的方案数为C(2n n),不填1的其余n位自动填以数0。从C(2n n)中减去不符合要求的方案数也是所求数量。不合要求的数指的是从左而右扫描,出现0的累计数超过1的累计数的数。不合要求的数的特征是从左而右扫描时,必然在某一奇数2m+1位上首先出现m+1个0和m个1。此后的2(n-m)-1位上有n-m个1,n-m-1个0。如若把后面这2(n-m)-1位之中的0与1交换,使之成为n-m个0,n-m-1个1,结果得 1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n-1个1和n+1个0组成的一个排列。反过来,任何一个 由n+1个0,n-1个1组成的2n位数,由于0的个数多2个,2n是偶数,故必定会在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分,令0 和1互换,使之成为由n个0和n个1组成的2n位数。即n+1个0和n-1个1组成的2n位数,必对应于一个不合要求的数。由上可知:【n+1个0和n-1个1组成的2n位数,与不符合要求的数是一一对应的】。所以不符合要求的数量为C(2n n+1),相减即可得结果。

同一问题两种解必然相等,所以递推式等于组合数之差,证毕。

【应用】之【阿里巴巴笔试题】:12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

【解答】:
把12个人按从低到高编号2,3,4,。。。,13(避免与0、1重复,或者你记为A、B、C、D。。。也行);
现在分类,把前排人归为类0,后排人归为类1,我们任意给出一个0和1的序列,比如:010101010101,约定该序列一定与2,3,4,。。。,13按顺序顺序对应,就是0、1序列中第一个对应2,第二个对应3。。。,排列时遇0排前排,遇1排后排,以此类推,那么这两排人就是:

后:3  5  7  9  11  13
前:2  4  6  8  10  12   //(1)

再给个序列:110000001111,令其与2,3,4,。。。,13对应,
那么这两排就变成:

后:4  5  6   7   8   9
前:2  3  10  11  12  13            //(2)

显然序列(1)符合要求,序列(2)不符合要求,因为前排10比后排6高。经过以上约定,我们现在集中解决什么样的序列是符合要求的序列?
这里直接给出【答案】:对0、1序列,必须满足从左向右扫描,任何时刻0的累计数不少于1的累计数(似曾相识?)。
比如这样一个序列00111(?)0001101,在处,不满足0的累计数不少于1的累计数,会出现这样的情况:

后:4  5  6    
前:2  3       //前5个人按我们的约定排出来

前五个数是这样排列的。问题来了,6放在后排,它对应的前排有吗?显然没有比6小的数字了,所以不符合题意。很容易归纳出来,但凡出现1的次数比0多,多出的1都没有比自己矮的前排了,所以以上答案是正确的。

这个答案对应的数值解是多少呢?请向上翻到【等价问题】,一模一样吧,解为h(6)!