出栈数量问题（卡塔兰数）

《数据结构》上有一个题目，问 4 节火车，进入一个岔道的出岔道的组合有多少种，我当时一看就不想做，如果有电脑在旁边，一个深搜就好了，可惜，没有，所以认认真真写了半天，才得到 14 种这个答案。

今天哈尔滨网赛前，无聊，研究一下，用半个小时写了一下这个深搜：

#include <stdio.h>
#include <stack>
#define N 25
using namespace std;

int res[N],pos,cnt,MaxN;
stack<int> st;

void test(int x){
  int i;
  if(pos==MaxN){//已经全部出去了，打印结果
    cnt++;
    printf("%5d:",cnt);
    for(i=0;i<pos-1;i++)
      printf("%3d",res[i]);
    printf("%3dn",res[i]);
    return;
  }
  //对于每一个新元素入栈，我们决策一下它前面的元素什么时候出栈
  if(!st.empty()){
    //一个个测试，当前栈顶的出去了
    res[pos++]=st.top();
    st.pop();
    //下一次递归再同样决策
    test(x);
    //递归返回了，把出去的拉回来
    st.push(res[--pos]);
  }
  if(x>MaxN)return;//大于MaxN的不考虑了
  //当前要决策的元素，可以加到栈里面了
  st.push(x);
  //决策下一个元素
  test(x+1);
  //状态还原，刚刚放进去的出来，好返回上一个数字继续找
  st.pop();
}

int main(){
  while(scanf("%d",&MaxN)!=EOF){
    if(MaxN<=N){
      pos=0;
      cnt=0;
      test(1);
    }else{
      printf("Max Input = %dn",N);
    }
  }
  return 0;
}

如书上题目要求的，MaxN=4 时的结果是：

4
1:  1  2  3  4
2:  1  2  4  3
3:  1  3  2  4
4:  1  3  4  2
5:  1  4  3  2
6:  2  1  3  4
7:  2  1  4  3
8:  2  3  1  4
9:  2  3  4  1
10:  2  4  3  1
11:  3  2  1  4
12:  3  2  4  1
13:  3  4  2  1
14:  4  3  2  1

再输出几个结果，发现出栈数目是爆炸增长的，再草稿纸上写了递推的关系，我是分 1 开始为开始元素，2 开始为开始元素，3 为开始元素……这样讨论的，分别是：f(n-1),f(n-1),f(n-2)+c(1,n-3)……反正，好复杂，我也不想去整理了，于是把输出的前 7 项“1 2 5 14 42 132 429”Google 之，发现这个数列是一个叫卡特兰的数列，看上去，应用还挺多的。在维基百科上，看到这个通项公式：

看上去就有点傻眼了，呃，我自认我不会推导出来~诶诶，数学没学好啊~

引用维基百科上的：

前几项为 （OEIS中的数列A000108）: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

哇咔咔，数据好大~