Catalan數 && 【NOIP2003】出棧序列統計

令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)

　　=C(2n, n)/(n+1)

　　=h(n-1)*2(2n-1)/(n+1)

具體推導請百度，這裡隻需記得推導公式為h(n)=h(n-1)*2(2n-1)/(n+1)即可。

我們來說說這個的應用吧，從catalan數的定義遞歸定義可以看出，它是由自己 本身的一部分和n減去一部分 的和得到的，也就是說，有n個物品，1個物品進行操作1，n-1個不同任意排列物品進行操作2，即有h(0)*h(n-1)中方式；2個不同任意排列物品進行操作1，n-2個不同任意排列物品進行操作2，即有h(1)*h(n-2)種方式（乘法原理）……，然後問，n個物品有多少種方式使得不同物品進行不同種操作。根據乘法原理和加法原理，學過dp的很容易就能推導出卡特蘭數的遞歸方程了。

應用：就如我上面所說。

例題：

1.括号化問題。

　　矩陣鍊乘： P=a1×a2×a3×……×an，依據乘法結合律，不改變其順序，隻用括号表示成對的乘積，試問有幾種括号化的方案？(h(n)種)

2.出棧次序問題。

　　一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列? (h(n)種)

　　類似：有2n個人排成一行進入劇場。入場費5元。其中隻有n個人有一張5元鈔票，另外n人隻有10元鈔票，劇院無其它鈔票，問有多少中方法使得隻要有10元的人買票，售票處就有5元的鈔票找零？(将持5元者到達視作将5元入棧，持10元者到達視作使棧中某5元出棧)

3.将多邊行劃分為三角形問題。

　　将一個凸多邊形區域分成三角形區域的方法數?

　　類似：一位大城市的律師在她住是以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果她從不穿越（但可以碰到）從家到辦公室的對角線，那麼有多少條可能的道路？

　　類似：在圓上選擇2n個點,将這些點成對連接配接起來使得所得到的n條線段不相交的方法數?

4.給頂節點組成二叉樹的問題。

　　給定N個節點，能構成多少種不同的二叉樹？（能構成h(N)個）

#include <cstdio>
using namespace std;

int main() {
	int n, ans=1;
	scanf("%d", &n);
	for(int i=2; i<=n; ++i)
		ans=ans*((i<<2)-2)/(i+1);
	printf("%d\n", ans);
	return 0;
}
      

本文為部落客原創文章，未經部落客允許不得轉載。一經發現，必将追究法律責任。