出栈序列的个数问题

当n个元素\(a_1,a_2,\cdots,a_n\)有序进栈,但不约束出栈时机,但是进栈一定按照排好的顺序,问一共有多少个出栈序列。

如何进行计算出栈序列的个数呢?

首先定义一个函数\(f(n)\),表示n个元素有序进栈时,可能的出栈序列个数

那么现在考虑一个问题在n个元素中,假设第i个元素 \( a_i \)是最后出栈的,这种情况下有多少种可能呢?

分析思路1

参考这篇博客

分析:设f(n)为“n个元素以一定的顺序入栈,出栈顺序的种类数”。显然f(1)=1,f(2)=2。我们现在来分析一般情况。一般情况下,我们可以按照“第一个入栈的元素,在出栈序列中的位置”作为分类手段。

举个例子,我们假设入栈元素为A,B,C,D。我们按照“A在出栈序列中的位置”分类讨论:

(1)当A第一个出栈时,A先进,然后马上出栈。这种情况下,共有“BCD出栈顺序的种类数”种方案。也就是f(n-1)。

(2)当A第二个出栈时,A先进,B再进,之后B需要马上出来(这样才能确保A排第二)。此时共有f(n-2)种方案。

(3)当A第三个出栈时,A先进,之后只要确保排在A后面两个的元素比A先出即可。此时共有f(2)*f(1)种方案。f(2)是指“BC入栈出栈顺序的种类数”,f(1)是指”D入栈出栈的种类数”。

分析思路2

按照分析最后出栈元素进行讨论

首先考虑 元素 \( a_i \) 进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 这些元素肯定都进过栈了,因为进栈是按照指定顺序的。在由于 \( a_i \) 是最后出栈的,而栈是先进后出、后进先出的特定,因此 \( a_i \) 进栈的时候,栈应该是空栈,否则 \( a_i \) 不可能是最后一个出栈,这也意味着 \(a_1,a_2,\cdots,a_{i-1}\) 这些元素在 \( a_i \) 进栈之前都已经出栈了。

总结一下就是当 \( a_i \) 是最后出栈的元素时, \( a_i \) 在进栈之前, \(a_1,a_2,\cdots,a_{i-1}\) 都已经完成了进栈和出栈,这就是一个符合我们函数定义的子问题 \(f(i-1)\)。

再考虑 \( a_i \)之后的元素,由于 \( a_i \) 是最后出栈的元素, \( a_i \) 元素进栈之后就只可能一直待在栈底,那么 \(a_{i+1},a_{i+2},\cdots,a_{n}\) 这些元素在 \( a_i \) 元素进栈之后完成了进栈和出栈的操作,这又是一个子问题f(n-i).

那么这样,当 \( a_i \) 是最后出栈的元素,那么这种前提下的可能出栈序列数目为 \( f(i-1) * f(n-i) \)

所以有 \( f(n)=\sum_{i=1}^n f(i-1) f(n-i) \)

实际这个是卡特兰数,有兴趣可以看看相关资料

令f(0)=f(1)=1这样可以正确进行递归过程

\( f(n)=C_{2n}^{n}-C_{2n}^{n-1}= \frac{ C_{2n}^{n} }{n+1} \)

相关推导可以参见下面的视频

个数是指数量级的。

参考文章:

https://blog.csdn.net/harryhare/article/details/69388827?skintest=skin3-template-test

https://blog.csdn.net/qq_26286193/article/details/80216479

发表评论

电子邮件地址不会被公开。 必填项已用*标注