数列与规律

探索规律的奥秘——括号序列摘要本文探讨了在一定限制条件下“合法括号序列”的数量。

使用几种不同的方法，先有条理地分析、探索出递推的规律，进而推导得出公式。

引入定义“括号序列”为一串由“(”和“)”组成的序列。

定义“合法的括号序列”为一个可以将“(”和“)”配对，从而满足以下条件的括号序列：1、“(”和“)”数量相等。

2、两对括号之间要么是包含关系（形如“(())”），要么互不相交（形如“()()”）.不难证明，一个合法的括号序列只有一种合法的配对方法。

接着，我们把一个括号序列写成“分行”形式：例如把()(()((())()))(())写成：()( )( )()( ) ()( )()()则我们定义“合法括号序列的深度”为其“分行”形式所占用的行数（例如以上序列的“深度”就是4）。

当然，也有更严谨的定义方法：“深度”就是原序列任意前缀中“(”和“)”数量之差的最大值。

也就是说，设原序列为A，从A的开头开始从左往右选取连续的一些字符，就能“截”出一串新的括号序列V（不一定合法），并求得V序列中“(”与“)”数量之差。

通过这种方式所能得到的最大的差，就是A序列的深度。

为什么？因为在“分行形式”中，从开头往右看，看到一个“(”就代表着“以后的字符向下进一行”，看到“)”就代表着“以后的字符向上回退一行”，两者相抵，所以把两者数量相减，就能得到V序列最后一个括号的深度。

这样的话，最深的括号的深度——也就是所得差的最大值——即为A序列的深度，也就是其分行形式占用的行数。

因此，以上两种对“深度”的定义等价。

问题来了：给定正整数N和K，找出一种高效的算法，用以求包含N对括号且深度为K的合法括号序列数量。

一种简单但是错误的算法显而易见，解决此问题的高效方法是递推。

但是，每次从哪几个数递推到那几个数？递推几次？按照什么规律递推？不难想到的一种方法是：首先，死算出N=1情况下的结果：当K=1，所求结果为1。

对应的序列有：()当K≠1，所求结果为0。

于是，把N=1时的所有序列：()在任意合法位置添加一对括号：()() (()) 新添加的用红色标记。

就不重不漏地得到了N=2时的所有序列。

故当N=2时：当K=1时，所求结果为1。

对应的序列有：()()当K=2时，所求结果为1。

对应的序列有：(())当K≠1且K≠2时，所求结果为0。

于是，把N=2时的所有序列： ()() (())在任意合法位置添加一对括号：()()() ((()))(()())(())()就不重不漏地得到了N=3时的所有序列？这下，我们发现了问题！图中标出的三对序列被重复计算了！所以，以上算法——虽然它可以通过改进来变得很高效——归根结底是错误的！让我们总结一下错因：在以上方法中，我们是如何得到某一个序列的？从最基本的“()”开始，我们不断在任意合法位置添加一对括号，最后得到所有序列。

但是，以这种方式，我们可以用多种顺序添加括号，来得到同一个序列，因而导致重复计算。

也就是说，导致错误的是，一个序列，有多种得到它的方法！所以，我们要适当调整添加括号的顺序，使得每一个序列有且仅有一种得到它的方法——至少在“不断添加括号”的思路下是如此。

一种正确但略显复杂的算法如何调整顺序呢？不难想到，可以“从左往右”添加括号。

位于同一个合法括号序列中的两对括号A和B，如果A的左括号在B的左括号左边，就说A在B左边；反之，就说A在B右边。

举个例子：对括号序列()(()((())()))(())，在“从左往右添加”的方法下，是这样得到它的：（新添加的用红色标出。

)1、()2、 ()()3、 ()(())4、 ()(()())5、 ()(()(()))6、 ()(()((())))7、 ()(()((())()))8、()(()((())()))()9、()(()((())()))(())这时，我们发现，在添加的过程中，出现了两种现象。

第一，每次，把当前序列中红色左括号右边（不包括它自己）的部分截取出来，那么其中一定全是“)”；第二，每次红色的一对括号的左右两半都是紧挨着的。

为什么？道理并不难。

第一：因为我们“从左往右”添加括号，所以每次添加的一对括号一定是“最右边”的一对。

又因为我们用左括号位置来判别两对括号之间的“左右”关系，所以新添加的左括号一定是最右边的左括号，进而，它的右边没有左括号，就全是右括号。

第二：因为红色左括号的右边全是右括号，所以如果红色右括号不是紧挨其右，红色的一对括号之间就有且仅有一些黑色右括号。

这样当前序列就不合法了，因为红色的一对括号与某些黑色括号部分相交。

因此，红色的左右括号必然紧邻。

事实上，只要简单地遵循以上两个原则添加红括号，就能做到“从左往右”添加。

让我们总结一下：1.我们从空序列“”开始；2.每次，我们在末尾连续的右括号之间或者在紧挨其左处；3.添加一对左右紧邻的新括号；4.就可以不重不漏地得到任意的合法括号序列。

这样，我们记为包含i 对括号、深度为j 、且末尾连续的“)”数量为p 的合法括号序列数量。

那么，对自然数i,j,p,（j ≥p ）我们可以得到递推式：⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧>=>++==>≠>>>>≤=====>>===-------=-∑)1,1()1,1(1),0,0,1()0,0(0)0(1)0,0(0)1,1(0)1(11,1,11,,1,,11,,1,,i j p i A A A j p i j p j p i A j p i p j i jp i jp i ijp A p j i j j i j j i jp m m j i pj解释一下其意思：对于第1行：当i=1,j=1,p=1时，易知只有一个合法序列： ()对于第2 、3、5行：这两种情况不存在合法序列。

对于第4行：当i=j=p=0,唯一的合法序列是空序列“”。

对于第6行：首先需要明确的是，p 不仅是序列末尾连续的“)”数量，也是序列中最右边一对括号的深度。

i >1表示括号数量不止一个；p>0,j>0是序列合法性的保证。

p ≠j 表示：最右边一对括号的深度不等于序列深度，也就是说，p j A ,,i最右边一对括号不是最深的，把它删去也不会减少序列深度。

所以说，把它删去会得到包含i-1对括号、深度仍为j 的括号序列。

至于删去后的p 值，分类讨论：当删去的左括号左边是另一个右括号时：p 不会减少，因为那一个右括号在最右边的一对括号被删去后会补齐被删去的右括号的位置。

p 会增加吗？可能，因为删去后， 来补齐空缺的可能不止一个右括号。

最多几个？不超过j,因为删去 后末尾连续的“)”数量不可能超过深度j 。

于是，此时删去后的p 值小于等于j ，大于等于原来的p 值。

当删去的左括号左边是另一个左括号时：因为此时没有 紧邻删去括号左边 的右括号来补齐空缺，p 值会由最右边一对括号的删去而减一。

此时，删去后的p 值是原来p 值减一。

综上，删去后的的p 值大于等于原来的p 值减一，小于等于j ；j 不变；i 减一。

此时反方向考虑：对于，p-1≤m ≤j,所有包含i-1对括号、深度为j 、末尾连续“）”的数量为m 的合法括号序列中，都有且仅有一个位置，使得：1、在该位置添加新括号符合上文讨论的“从左往右”的添加原则；2、在该位置添加一对新括号能产生一个包含i 对括号、深度为j 、末尾连续“）”的数量为p 的合法括号序列。

同时，通过这种方式得到的所有新的合法括号序列，不重不漏地组成了所有包含i 对括号、深度为j 、末尾连续“）”的数量为p 的合法括号序列的集合。

也就是说。

对于第7行：由p=j=1可知，第五行所表示的括号序列必然都形如()()()...()()()也就是说，任意两对括号之间互不相交。

易知，此时只有一个合法序列，所以对于第8行：i>1表示括号序列包含超过一对括号；p=j 表示最后一对括号的深度和序列深度相等，也就是说最后一对括号是序列中最深的括号之一；j>1表示序列深度大于1。

首先，要是把最右边一对括号删去的话，i 会减一。

而j 和p 呢？分类讨论:当最后一对括号是序列中唯一的最深的括号时：要是把这对括号删去的话，新序列的深度必然减少1，即j 会减一。

接着，因为原先j=p,又有j ≥p 恒成立，而j 又减了一，所以p 至少也减一。

同时，因为只删去了一对括号，p 至多减一。

所以，p 一定恰好减一。

当最后一对括号是序列中（超过一对的）最深括号之一时：要是把这对括号删去的话，新序列的深度j 不变。

),0,0,1(j p j p i ≠>>>=p j A ,,i ),0,0,1(1,,1j p j p i A j p m m j i ≠>>>∑-=-=p j A ,,i )1,1(1==>j p i首先，新的p 小于等于新的j ，所以p 的值不会增加。

同时，因为 只删去了一对括号，所以新的p 相较原来至多减少1。

因此，p 要么不变，要么减一。

尝试后发现，两种情况都可能发生。

综上，有三种可能发生的情况：1.i 减一，j 减一，p 减一；2.i 减一，j 不变，p 减一；3.i 减一，j 不变，p 不变。

此时再反方向思考：原先，我们通过删去最右边的括号从所有包含i 对括号、深度为j 、末尾连续“)”数量为p 的所有合法括号序列得到以上三种情况；所以我们也可以通过以唯一的方式添加最右边的括号来从以上三种情况不重不漏地得出所有包含i 对括号、深度为j 、末尾连续“)”数量为p 的所有合法括号序列。

因此也就不难理解了。

综上，我们找出了规律，列出了递推式，就可以按照这个式子来高效计算了。

然而，还有一个永恒的问题：我们可以做得更好吗？事实上，可以。

我们注意到原先的递推式中出现了求和运算，需要一个个相加才能完成，当数值很大或需要相加的数很多的时候十分繁琐。

我们可以通过以下方式改进它。

我们令∑==p m m j i p j i A B 0,,,,，那么原递推式中就可以用2,,1,,1----p j i j j i B B 来代替了，原本繁琐的多次加法运算就被化为一次减法运算。

而我们所额外要做的，就是维护B 。

事实上，每次算出一个，我们就可以按照递推式⎪⎩⎪⎨⎧>+==-)0()0(1,,,,,,,,p B A p A B p j i pj i p j i p j i 来简单易行地维护B 。

好了，目前为止，我们已经借助问题中的内在规律找到了一种十分高效的解决此问题的方法。

但是，我们还可以做得更好吗？答案是肯定的。

一种正确、高效且巧妙的算法我们一直在采用“不断添加”的思路来解题，是时候换一换了。

我们记j i A ,为包含i 对括号、深度为j 的合法括号序列数量，当i 、j 非常大时，计算j i A ,就是一项庞大的工程。