卡塔兰数是数论中的一种特殊数列，可以看作是组合数的拓展数列
数列前面几项是这样：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640…

递推的公式有：

$$\begin{align*} & f(n)= \sum^{n-1}_{i=0} f(i)*f(n-i-1) \\\\ & f(n)= \frac{f(n-1)*f(4*n-2)}{n+1} \\\\ & f(n)= \frac{C^n_{2n}}{n+1} \\\\ & f(n)= C^n_{2n}-C^{n-1}_{2n} \\\\ \end{align*}$$

---

适用卡塔兰数的一些模型：

1多0序列个数： 有一个长度为$2n$的$01$序列，其中$1,0$各$n$个，要求数列的前k$(k∈[1,2n])$个数中，1的个数不少于0。合法的序列个数就是卡塔兰数的第n项。
给定节点数目的二叉树形态： 一棵n个节点的二叉树的形态总数，就是卡特兰数的第n项
矩阵连乘： $ P = a_1×a_2×a_3×……×a_n $，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，其括号化的方案数目就是卡塔兰数的第n项。
出栈次序： 一个栈(无穷大)的进栈序列为$1，2，3，…n$，其不同的出栈序列的数目就是卡塔兰数的第n项。
凸多边形三角划分： 在一个边数为n的凸多边形中，通过若干条互不相交的对角线把这个多边形划分成了若干个三角形。不同划分的方案数就是卡塔兰数的第n项。
拓展一下，也可以变成在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数。
n对括号正确匹配数目： 给定n对括号并将括号正确配对的字符串(也就是最终字符串合法)数为卡塔兰数的第n项。
不穿对角线路径： 在一个n×n格点网络中，一条从左下角走到右上角的不越过对角线的单调路径的数目为卡塔兰数的第n项。
阶梯填充： 一个高度为n的阶梯状图形(网格对角线的上半部分)用长宽任意的矩形来完美填充，方案个数为卡塔兰数的第n项。

---

递推代码

#include<bits/stdc++.h> 
using namespace std;
long long n,mod=1e9+7,h[1000010],inv[1000010];
void init1()
{
    h[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            h[i]=(h[i]+h[j]*h[i-j-1])%mod;
}
void init2()
{
    h[0]=1;
    inv[1]=1;
    for(int i=2;i<=n+1;i++)inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)h[i]=(h[i-1]*(4*i-2)*inv[i+1])%mod;
}
int main()
{
    cin>>n;
    //init1();
    init2();
    for(int i=0;i<=n;i++)cout<<h[i]<<' ';cout<<endl;
	return 0;
}