Catalan数列的详细介绍（总结版）
需积分: 45 44 浏览量
2010-01-27
13:16:08
上传
评论
收藏 42KB DOC 举报
Catalan 公式是这样的
f(n)=f(1)*f(n-1)+f(2)*f(n-2)+f(3)*f(n-3)+......+f(n-1)*f(1)
前 16 个:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 (在处理数据的过程
中应该用到高精度）
Catalan 数列[转贴]
看下面两个例题:
将一个凸多边形区域分成三角形区域的方法数?
令 hn 表示具有 n+1 条边的凸多边形区域分成三角形的方法数。同时令 h1=1，则 hn 满足递推关
系
hn=h1hn-1+h2hn-2+...+hn-1h1(n>=2)(想一想,为什么?)
该递推关系的解为 hn=c(2n-2,n-1)/n (n=1,2,3,...)
其对应的序列为 1,1,2,5,14,42,132,....从第二项开始分别是三边形,四边形,...的分法数
"即 k 边形分成三角形的方法数为 hk=c(2k-4,k-2)/(k-1)(k>=3)
n 个+1 和 n 个-1 构成 2n 项a1,a2,...,a2n" "" "
其部分和满足 a1+a2+...+ak>=0(k=1,2,3,..,2n)对与 n 该数列为
Cn=c(2k,k)/(k+1)""(k>=0)" " 对应的序列为1,1,2,5,14,42,132,...
序列 1,1,2,5,14,42,132,....叫 Catalan 数列。
下列问题都是 Catalan 数列:
1.有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10
元钞票，
剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
2.一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。
如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3.在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数?
4.n 个结点可够造多少个不同的二叉树?
5.一个栈(无穷大)的进栈序列为 1,2,3,..n,有多少个不同的出栈序列?
[附]生成程序[原创]
""var
"""" a,b:array[1..100]of int64;
"""" n,k,r,i,ji:longint;
"" begin
"""" readln(n);
"""" if (n=1)or(n=2) then begin writeln(1);halt;end ;
"""" r:=n-1;
"""" k:=2*(n-1);
"" for i:=1 to r do
""" begin
""""" a[i]:=i;
""""" b[i]:=k-r+i;
""" end;
""" k:=r;
""" ji:=0;
""" " repeat
if k=r then ji:=ji+1;
""" if a[k]<b[k] then begin a[k]:=a[k]
+1;
""""""""""""""""""""""" if k<r then for
k:=k+1 to r do
""""""""""""""""""""""""""""""""""""""" a[k]:=a[k-
1]+1;
""""""""""""""""""" end
""""""""""""""""""" else k:=k-1;
until k=0;
writeln(ji div n);
end.其实这样写是最最最笨的方法,可以
直接用 C 的性质写,不用把每一个 C 求出
来...
资源评论
