卡塔兰数

常用公式

h(n) = h(n-1)*2(2n-1)/(n+1)，h(0)=0，n>=1

常见应用

栈的出栈次序 — h(n)

概述

入栈顺序为1,2,3 … n 时，出栈顺序有h(n)种。

分析

1. n=1，1种
   • 1入栈再出栈。[1]
2. n=2，2种
   • 1入栈出栈，2入栈出栈。[1,2]
   • 1入栈，2入栈，2出栈，1出栈。[2,1]
3. n=3，5种
   • 1入栈出栈，2入栈出栈，3入栈出栈。[1,2,3]
   • 1入栈出栈，2入栈，3入栈，3出栈，2出栈。[1,3,2]
   • 1入栈，2入栈，2出栈，1出栈，3入栈，3出栈。[2,1,3]
   • 1入栈，2入栈，2出栈，3入栈，3出栈，1出栈。[2,3,1]
   • 1入栈，2入栈，3入栈，3出栈，2出栈，1出栈。[3,2,1]

……

为什么n=3时，出栈顺序无法实现[3,1,2]？
因为若3是第一个出栈，则代表1，2肯定没出栈，要不然第一个出栈的就是1或2而不是3。由于入栈顺序固定为[1，2，3] ，出栈顺序只能为[3,2,1]。

不同的二叉搜索树个数 — h(n)

概述

二叉搜索树由结点值分别为[1,n]的n个结点构成，一共能构成h(n)个不同的二叉搜索树

分析

其中的二叉树序列用层序遍历得到

1. n=1
   • [1]
2. n=2
   • [2,1]
   • [1,null,2]
3. n=3
   • [1,null,2,null,3]，[1,null,3,2,null]
   • [2,1,3]
   • [3,2,null,1,null] ，[3,1,null,null,2]

……

代码实现

通过代码实现已知n求h(n)

public int catalan(int n){	// n >= 1
	long h = 1;//用long防止计算过程中类型溢出。h(0) = 1
	for(int i = 1; i <= n; i++){
		h = h*2*(2*i-1)/(i+1);
	}
	return (int)h;
}