_001_Stack_10Exercises-2

组合数学中的Catalan数， C(2n,n)/(n+1) （C(2n,n)表示2n里取n）
  
证明下是卡塔兰数 
使用递归法证明：
设f（n）为n个数栈混洗可能的结果。
对于一组数 1,2,3,4,5,...,k.,..,n
假设最后出栈的元素为k
过程一：那么k之前有 k-1个数比k小，对于这k-1个数，在k入栈之前，已经入栈且出栈，栈混洗可能的结果是 f(k-1)。
过程二：那么k之后有 n-k个数比k大，对于这n-k个数，在k出栈之前，已经入栈且出栈，栈混洗可能的结果是f(n-k)。
这两个过程独立，对于此时的k，可能的排列有 f(k-1)* f(n-k) 种。
又因为 k的取值为1,2,3,...,n。所以有：
解这个递归式子，解得：f(n) =C(2n,n)/(n+1)
证明完成。
ps：直接求解这个递归式有一定难度，不过我们可以使用数学归纳法证明结果的正确性。
先计算f(0)正确，再假设f(n-1)正确，最后证明f(n)正确。详细过程就不写啦。