跳转至

2、卡特兰数

简述

​ 卡特兰数又称卡塔兰数，它是组合数学中一个常出现在各种计数问题中出现的数列，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ......

1.递归公式1 f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)

2.递归公式2 f(n)=\frac{f(n-1)*(4*n-2)}{(n+1)}

3.组合公式1 f(n)=\frac{C_2_n^n}{n+1}

4.组合公式 2 f(n)=C_2_n^n-C_2_n^{n-1}

5.增长趋势 f(n)\sim \frac{4^n}{{n^{\frac{3}{2}}}\sqrt{\pi }}

应用

二叉树的计数：已知二叉树有 n 个结点，求能构成多少种不同的二叉树

括号化问题：一个合法的表达式由()包围，()可以嵌套和连接，如：(())()也是合法表达式，现给出 n 对括号，求可以组成的合法表达式的个数

划分问题：将一个凸 n+2 多边形区域分成三角形区域的方法数

出栈问题：一个栈的进栈序列为1,2,3,..n，求不同的出栈序列有多少种

路径问题：在 n*n 的方格地图中，从一个角到另外一个角，求不跨越对角线的路径数有多少种

握手问题：2n 个人均匀坐在一个圆桌边上，某个时刻所有人同时与另一个人握手，要求手之间不能交叉，求共有多少种握手方法

f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
long long cat[50];
long long Cat1(int n)
{
    memset(cat,0,sizeof(cat));
    cat[0]=cat[1]=1;
    for(int i=2;i<=n;++i)
    {
        for(int j=0;j<i;++j)
            cat[i]+=cat[j]*cat[i-j-1];
    }
    return cat[n];
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%lld\n",Cat1(n));
    return 0;
}

f(n)=\frac{f(n-1)*(4*n-2)}{(n+1)}

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
long long cat[50];
long long Cat2(int n)
{
    memset(cat,0,sizeof(cat));
    cat[0]=1;
    for(int i=1;i<=n;++i)
    {
        cat[i]=((cat[i-1])*(i*4-2))/(i+1);
    }
    return cat[n];
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%lld\n",Cat2(n));
    return 0;
}

f(n)=\frac{C_2_n^n}{n+1}

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
long long cat[50];
long long tatal;
void Cat3(int n)
{
    tatal=1;
    for(int i=0;i<n;++i)//求c(2n,n);
        tatal=tatal*(2*n-i)/(i+1);
    tatal/=(n+1);
}
int main()
{
    int n;
    scanf("%d",&n);
    Cat3(n);
    printf("%lld\n",tatal);
    return 0;
}

f(n)=C_2_n^n-C_2_n^{n-1}

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
long long cat[50];
long long tatal;
void Cat4(int n)
{
    tatal=1;
    for(int i=0;i<n;++i)//求c(2n,n);
        tatal=tatal*(2*n-i)/(i+1);
    tatal=tatal-tatal*n/(n+1);
}
int main()
{
    int n;
    scanf("%d",&n);
    Cat4(n);
    printf("%lld\n",tatal);
    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用