问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深。

问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排。
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案。
比如000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个。
每个1前面的零的个数要大于它前面1的个数。
OK,问题已经解决.
如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个。
这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举多边形分成三角形的个数圆括弧插入公式中的方法数,其通项是c(2n, n)/(n+1)

---------------------------------------------

证明:

在这里先介绍一下好括号序列

好括号序列是指它有n个的左括号和n个右括号组成,在这个序列中任意找一个空,左边的序列中右括号数目一定不超过左括号数。

下面介绍求证有n个左括号组成的好括号列的个数为

Cn = C(2n, n) / (n+1)

证:n个左括号n个右括号组成的括号序列共计C(2n, n)个。只要算出n个左括号n个右括号组成的坏括号序列的个数,即可得到好括号序列的个数。

设a1,a2,a3,。。。a2n是n个左括号n个右括号组成的坏括号序列。

其中必存在一个最小的j使得a1,a2,。。。aj中右括号比左括号多1个。把aj+1,aj+2.。。。a2n的左括号变成右括号,右括号变成左括号。这时共有n-1个左括号,n+1个右括号;上述变换的过程是可逆的。

也就是说n-1个左括号,n+1个右括号的坏括号序列,也存在一个j使得a[j]里面右括号比左括号多一个;同理把a[j]后面的a[j+1], a[j+2]...里面左右互换,就是一个n个左括号n个右括号的坏括号序列了。

故n个左括号n个右括号组成的坏括号的序列与n-1个左括号n+1个有括号组成的坏括号一一对应,即相等。

而n-1个左括号n+1个有括号组成的坏括号得数目是C(2n, n+1).

则得n个左括号n个右括号组成好括号的序列个数有:

c(n)=C(2n, n) - C(2n, n+1)= C(2n, n) / (n+1)

这也是著名的catalan数。

下面讨论已知入栈顺序的n个元素求合理的出栈序列有多少种

将左括号换成元素的进栈,右括号换成元素出栈。好括号的规律刚好对应于栈中没有元素的时候不可以出栈。

则出栈的序列刚好等于catalan数。

参考链接:http://www.cnblogs.com/xiawen/archive/2013/05/04/3058973.html

标签: none

添加新评论