目录
卡特兰数公式
f(n) = C(2n,n) / (n+1)- 计算用途：二叉树形态数，出栈序列数
出栈序列数
【例 1】3 个不同元素依次进栈，能得到多少种不同的出栈序列？
【解】
f(3) = C(6,3) / (3+1) = 20 / 4 = 5
【例 2】5 个不同元素依次进栈，能得到多少种不同的出栈序列？
【解】
f(5) = C(10,5) / (5+1) = (6 * 7 * 6) / 6 = 42
二叉树形态数
【例】先序序列（前序序列）为 a, b, c, d 的不同二叉树的个数是？
【解】前序序列为入栈次序，中序序列为出栈序列，因为前序序列和中序序列可以唯一确定一棵二叉树，所以相当于“以序列 a, b, c, d 为入栈次序，则出栈序列的个数是？”
f(4) = C(8,4) / (4+1) = 70 / 5 = 14