カトラン数まとめ

h(1)=1,h(0)=1,catalan数(カトラン数)を再帰式を満たす.
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n−1)h(0)(ここでn>=2)
別の再帰式:
h(n)=((4*n-2)/(n+1))*h(n-1);
C++実装再帰プログラムは以下の通りである.

double Katelan(int m);
double Katelan(int m)
{
		if(m<0) return 0;
		if(m==0) return 1.0;
		if(m==1) return 1.0;
		//if(m>=2) return (double)(4*m-2)/(m+1)*Katelan(m-1);
		if(m>=2) return (double)Katelan(m-1)*(4*m-2)/(m+1);
}
int main(int argc, char *argv[])
{
	for(int i = 0; i<=10;i++)
	{
		cout<

この繰返し関係の解は、次のとおりです.
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
カトラン数の応用(実質的には再帰等式の応用)
1、括弧化問題マトリクスチェーン乗:P=a 1×a2×a3×……×an,乗算結合法則に基づいて,その順序を変えずに括弧だけで対の積を表すが,いくつかの括弧化案があるかどうか.(h(n)種)
2、スタックの順序の問題1つのスタック(無限大)のスタックのシーケンスは1,2,3,...,nで、いくつの異なるスタックのシーケンスがありますか?
3、
凸多角形の三角断面問題
ひとつを求めて
凸多角形
領域を三角形領域に分割する方法の数.
4、与えられたノードで二叉木を構成する問題N個のノードを与えて、何種類の異なる二叉木を構成することができますか?
二叉木問題の分析では、n=1の場合、1つのルートノードしかないと、1つの形態の二叉木しか構成できず、n個のノードで構成可能な二叉木の数をh(n)と表し、h(1)=1とする.h(0)=0;
n=2の場合,1つのルートノードが固定され,2−1個のノードがある.このノードは(1,0),(0,1)の2つのグループに分けることができる.すなわち,左に1個,右に0個,あるいは左に0個,右に1個である.すなわち,h(2)=h(0)*h(1)*h(1)*h(0)=2であり,2つの形態の二叉木を構成することができる.
n=3の場合、1つのルートノードが固定され、2つのノードがある.この2つのノードは、(2,0),(1,1),(0,2)の3つのグループに分けることができる.すなわち、h(3)=h(0)*h(2)+h(1)+h(2)*h(2)*h(0)=5であり、5つの形態の二叉木を構成することができる.
このように、n>=2の場合、構成可能な二叉木の数はh(n)=h(0)*h(n−1)+h(1)*h(n−2)+・・+であるh(n−1)*h(0)種,すなわちCatalan数の定義に合致し,通項式を直接利用して結果を得ることができる.
h(1)=1,h(0)=1,catalan数(カトラン数)を再帰式を満たす.
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n−1)h(0)(ここでn>=2)