卡特兰数——sgu130Circle

组合问题里比较常用的数列

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862……

令h(1)＝1,h(0)=1，catalan数满足递归式：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)

另类递归式：

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

#include<stdio.h>

int main()
{
    int k;
    scanf("%d",&k);
    int i,j;
    __int64 all=1;
    
    for(i=1;i<=k;i++)
    {
        all=(all*(4*i-2)/(i+1));
    }
    printf("%I64d %d\n",all,k+1);
}