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

《数据结构》上有一个题目，问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, …

哇咔咔，数据好大~