AcWing 3691：有向树形态 ← 卡特兰数 + 复旦大学考研机试题

【题目来源】
https://www.acwing.com/problem/content/3694/

【题目描述】
求 N 个相同结点能够组成的二叉树的个数。

【输入格式】
一个整数 N。

【输出格式】
输出能组成的二叉树的个数。

【数据范围】
1≤N≤20

【输入样例】
3

【输出样例】
5

【算法分析】
● 卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。若从第 0 项开始，则卡特兰数列 h[n] 为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, …。

● 常用的卡特兰数列 h[n] 有如下 4 种等价的递推式
h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1)
h[n]=h[n−1]*(4*n−2)/(n+1), (n≥2)
h[n]=C(2n,n)−C(2n,n−1), (n=0,1,2,...)
h[n]=C(2n,n)/(n+1), (n=0,1,2,...)

● 卡特兰数的第 20 项为 6564120420，大于 2×10^9，所以代码中要声明为 long long 型。

●​​​​​​​ 二叉树是有向树
（1）左子树的结点数为 0，右子树的结点数为 n-1。左子树的结点数为 1，右子树的结点数为 n-2。左子树的结点数为 n-1，右子树的结点数为 0。依此类推，可得“左子树的结点数为 k，右子树的结点数为 n-k-1”。

（2）显然，若设 h[k] 表示 k 个结点组成的二叉树的个数，那么由 n 个结点组成的二叉树的个数为 h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0]，且 h[0]=h[1]=1。显然就是上文卡特兰数的第一个通项公式。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=25;
long long c[maxn];
int n;int main() {cin>>n;c[0]=1,c[1]=1;for(int i=2; i<=n; i++)for(int j=0; j<=i-1; j++)c[i]+=c[j]*c[i-j-1];cout<<c[n];return 0;
}/*
in:
3out:
5
*/

【参考文献】
https://www.acwing.com/solution/content/104520/
https://blog.csdn.net/hnjzsyjyj/article/details/129148916