有n个数1,2,3,4,...n依次入栈,不必等全部的数入完再出,问有多少个出栈顺序?
解:
设问题答案是(f(n),f(1)=1,f(2)=2)
分n种情况:
1最后出来:(f(n))
k最后出来: (f(k-1)*f(n-k))
所以
(f(n+1)=f(n)+f(n-1)f(1)+f(n-2)f(2)+......+f(n-k)f(k)+.....f(n))
这是Catalan数的递推式:
得:(color{red}{f(n)=frac{C^{n}_{2n}}{n+1}})
有n个数1,2,3,4,...n依次入栈,不必等全部的数入完再出,问有多少个出栈顺序?
解:
设问题答案是(f(n),f(1)=1,f(2)=2)
分n种情况:
1最后出来:(f(n))
k最后出来: (f(k-1)*f(n-k))
所以
(f(n+1)=f(n)+f(n-1)f(1)+f(n-2)f(2)+......+f(n-k)f(k)+.....f(n))
这是Catalan数的递推式:
得:(color{red}{f(n)=frac{C^{n}_{2n}}{n+1}})