数据结构进栈出栈顺序问题

应该是这个 catalan number 【 在 DestinyWEI (微微☆SMILE) 的大作中提到: 】 : 不知道以前有没有人问过，我们好几个人讨论半天也没讨论出个所以然来，所以过来看看有没有牛人可以给解决一下，先谢过了。做数据结构卷子，有道题说7个元素（1234567）进栈有多少种出栈可能，还有10个元素进栈有多少中出栈可能，这个是不是有什么递推公式啊，求指点！！

方案1: 问题转化为01串问题(1代表进栈,0代表出栈),然后用公式或者动规求解 方案2: 递推 f[n]表示n个数的进出栈顺序总数,考虑第一个数出栈的位置则有如下递推式: 第一个数排在第1的位置:f[0]*f[n-1] 第一个数排在第2的位置:f[1]*f[n-2] ...... 第一个数排在第i的位置:f[i-1]*[n-i] f[n]=f[0]*f[n-1]+f[1]*f[n-2]+......+f[n-1]*f[0],其中f[0]=f[1]=1 【 在 DestinyWEI 的大作中提到: 】 : 不知道以前有没有人问过，我们好几个人讨论半天也没讨论出个所以然来，所以过来看看有没有牛人可以给解决一下，先谢过了。做数据结构卷子，有道题说7个元素（1234567）进栈有多少种出栈可能，还有10个元素进栈有多少中出栈可能，这个是不是有什么递推公式啊，求指点！！！ : --

万分感谢！！！ 【 在 xieys 的大作中提到: 】 : 方案1: : 问题转化为01串问题(1代表进栈,0代表出栈),然后用公式或者动规求解 : 方案2: : ...................

令h(1)＝1,h(0)=1，catalan数满足递归式： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2) 另类递归式： h(n)=((4*n-2)/(n+1))*h(n-1); 该递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...)