N个元素进栈 出栈情况种数

1.逐一求解

面对此类问题 我们无法直接分析元素个数 为N的情况 通常我们都会逐一分析

设定一个函数 f(N):N为元素个数 f(N)为出栈顺序种数 
1

显然:

f(1) = 1:a

f(2) = 2:a,b b,a

f(3) = 5:a,b,c  a,c,b   b,a,c   b,c,a    /*c,a,b*/   c,b,a

f(4) = ?
1
2
3
4
5
6
7

当N为4时 问题趋于复杂 那么怎么解决呢?
我们从小就开始学数学 小学数学有一章是–找规律
很明显 这种问题就是找规律的
只不过有些规律难找 我们一一研究

接下来我会以新口吻来分析这个问题 各位一看便知
假定f(0) = 1

f(1) = 1:a
a第1个出栈 前面有0个出栈 后面有0个出栈  f(0) * f(0) = 1  f(1) = 1

f(2) = 2:a,b b,a
a第1个出栈 前面有0个出栈 后面有1个出栈  f(0) * f(1) = 1
a第2个出栈 前面有1个出栈 后面有0个出栈  f(1) * f(0) = 1   f(2) = 2

f(3) = 5:a,b,c  a,c,b   b,a,c   b,c,a    /*c,a,b*/   c,b,a
a第1个出栈 前面有0个出栈 后面有2个出栈  f(0) * f(2) = 2
a第2个出栈 前面有1个出栈 后面有1个出栈  f(1) * f(1) = 1
a第3个出栈 前面有2个出栈 后面有0个出栈  f(2) * f(0) = 2  f(3) = 5


f(4) = ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

类似于递归思想 将难解的大问题转换为易于求解的子问题 一一求解
那么f(4)是多少呢? 这时就很容易解决了

A第1个出栈，前面有0个出栈  后面有3个出栈    f(0) * f(3) = 5
A第2个出栈，前面有1个出栈  后面有2个出栈    f(1) * f(2) = 2
A第3个出栈，前面有2个出栈  后面有1个出栈    f(2) * f(1) = 2
A第4个出栈，前面有3个出栈  后面有0个出栈    f(3) * f(0) = 5  f(4) = 14
1
2
3
4

递推:

f(n) = f(0)f(n-1) + f(1)f(n-2) + .....+ f(n-1)f(0)
1

2.卡特兰数的引入

那么这个数等于多少呢?实际上 早有先人研究过这一类数学问题 这个数就是著名的卡特兰数
以下内容来源于百度卡特兰数

3.得出结论

n个元素进栈，出栈情况种数为