卡特兰数 Catalan 笔记

时间：2023-03-09 06:59:36
卡特兰数 Catalan 笔记

一.公式

卡特兰数一般公式

　　令h(0)=1,h(1)=1，catalan数满足递推式。h(n) = h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)。也就是说，如果能把公式化成上面这种形式的数，就是卡特兰数。

组合公式

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

　　(化简前 h(n) = c(2n,n)-c(2n,n+1) (n=0,1,2,...) 证明)

递归公式1

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

递归公式2

　　h(n) = ∑(i=0 to n-1) h(i)*h(n-i-1)

二.资料

　　catalan---卡特兰数(小结)

三.某些题

1.在圆上选择2n个等间隔的点。证明将这些点成对连接起来使得所得到的n条线段不相交的方法数等于第n个Catalan数

设方法数为gn，分别将这些点用1，2，…，2n标记。取定点1，任选另一个偶数点2k，连接点1与点2k。该线段将圆分成K1和K2两部分。对K1，有k-1对点，故有gk-1种方法；对K2，有n-k对点，故有gn-k种方法。所以
   g0=1
   令hn=gn-1，则
   hn+1=h1hn+h2hn-1+…+hnh1  h1=1

所以gn=g0 gn-1 + g1 gn-1 +...+ gn-1 g0

即 gn=Cn

2.二叉树计数：一个有n个结点的二叉树总共有多少种形态

 //设当前根节点为k，方案数为h[k]，左子树有k-1个节点，右子树有n-k个节点

 //则 h[k]=h[k-1]*h[n-k](k=1 to n)

 //Ans= h[0]h[n-1] + h[1]h[n-2] +...+ h[n-1][0]

 //即卡特兰数

 #include<cstdio>

 #include<cctype>

 using namespace std;

 const int N=;

 int n;

 long long H[N];

 int read()

 {

     int now=;bool f=;char c=getchar();

     for(;!isdigit(c);c=getchar())

       if(c=='-') f=;

     for(;isdigit(c);c=getchar())

       now=(now<<)+(now<<)+c-'';

     return f?-now:now;

 }

 int main()

 {

     n=read();

     H[]=;

     for(int i=;i<=n;++i)

       H[i]=H[i-]*(*i-)/(i+);

     printf("%lld",H[n]);

     return ;

 }

3.出栈次序：一个栈（无穷大）的进栈次序为1、2、3……n。不同的出栈次序有几种。

　　我们可以这样想，假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数，一共有h(k-1)种方案。比k晚进栈且早出栈的有n-k个数，一共有h(n-k)种方案。所以一共有h(k-1)*h(n-k)种方案。显而易见，k取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。k的取值范围为1至n，所以结果就为h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0)。(转自Blog)
 //设k为最后一个出栈的数，

 //有k-1个比k早进栈且比k早出栈，有C[k-1]种方案

 //有n-k个比k晚进栈但比k早出栈，有C[n-k]种方案

 //根据乘法原理，C[k]=C[k-1]*C[n-k](k=1 to n)

 //Ans = C[0]C[n-1] + C[1][n-2] +...+ C[n-1][0]

 #include<cstdio>

 using namespace std;

 const int N=;

 int n;

 long long Ca[N];

 int main()

 {

     scanf("%d",&n);

     Ca[]=;

     for(int i=;i<=n;++i)

       Ca[i]=Ca[i-]*(*i-)/(i+);

     printf("%lld",Ca[n]);

     return ;

 }

注：

　　long long最大只能到33

Code：

 Ca[]=;

 for(int i=;i<=n;++i)

     Ca[i]=Ca[i-]*(*i-)/(i+);

Catalan

高精：

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 using namespace std;

 const int p=,mod=;

 int C[];

 inline int read()

 {

     int now=;bool f=;char c=getchar();

     for(;!isdigit(c);c=getchar())

       if(c=='-') f=;

     for(;isdigit(c);c=getchar())

       now=(now<<)+(now<<)+c-'';

     return f?-now:now;

 }

 void Print(int n[])

 {

     printf("%d",n[n[]]);

     for(int i=n[]-;i;--i)

       printf("%0*d",p,n[i]);

     puts("");

 }

 void Mult(int n[],int t)

 {

     int x=;

     ++n[];

     for(int i=;i<=n[];++i)

     {

         n[i]=n[i]*t+x;

 //        printf("%d:%d\n",i,n[i]);

         x=n[i]/mod;

         n[i]%=mod;

     }

     while(!n[n[]] && n[]>) --n[];

 //    Print(n);

 }

 void Div(int n[],int t)

 {

     int x=;

     for(int i=n[];i;--i)

     {

         n[i]=x*mod+n[i];

         x=n[i]%t;

         n[i]/=t;

     }

     while(!n[n[]] && n[]>) --n[];

 //    Print(n);

 }

 int main()

 {

     int n=read();

     C[]=;

     C[]=;

     for(int i=;i<=n;++i)

     {

 //        C[now]=C[now-1]*(4*i-2)/(i+1);

 //        printf("\n%d:\n",i);

         Mult(C,*i-);

         Div(C,i+);

 //        Print(C);

     }

     Print(C);

     return ;

 }

CODEVS.3113.二叉树计数2

相关文章