算法-数论-卡特兰数

我会带着你远行 2022-08-04 13:34 200阅读 0赞

***卡塔兰数***是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。  
令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)***

例如：h(2)=h(0)\*h(1)+h(1)\*h(0)=1\*1+1\*1=2

>   h(3)=h(0)\*h(2)+h(1)\*h(1)+h(2)\*h(0)=1\*2+1\*1+2\*1=5

另类递推式 ：

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

递推关系的另类解为：

> ***h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)***

***应用*  
1.括号化**

> 矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，
> 
> 试问有几种括号化的方案？(h(n-1)种)

**2.出栈次序**

> 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

**3.凸多边形三角划分**

> 在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。
> 
> 任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。

**4.给定节点组成二叉树**

> 给定N个节点，能构成多少种不同的二叉树？（能构成h（N）个,这个公式的下标是从h(0)=1开始的）

***以下是这两种递推关系求卡特兰数***

#include<stdio.h>
    int main(){
    	int n,i,catalan=1,itme=1;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	{
    		itme=catalan*(4*i-2)/(i+1);
    		catalan=itme;
    	}
    	printf("%d\n",catalan);
    	return 0;
    }

#include<stdio.h>
    int com(int n, int r)
    {
          long long i,j,s=1;
          if(n-r>r) 
    	  r=n-r; 
          for(i=0,j=1;i<r;i++)
          {
    	  s*=(n-i);
    	  for(;j<=r&&s%j==0;j++) 
    	      s/=j;
          }
          return s;
    }
    int main(){
    	int n;
    	long long catalan=0;
    	scanf("%d",&n);
    	catalan=com(2*n,n)-com(2*n,n+1);
    	printf("%d\n",catalan);
    	return 0;
    }