Module: 加泰罗尼亚数字


Problem

1 /2


加泰罗尼亚数字的数量

Theory Click to read/hide

加泰罗尼亚数字出现在哪里?
 

-给定括号对数的psp数量
-给定叶子数的二叉树的数量
-n*n方格中从左下角到右上角不碰到对角线的路径数

-n边形分成三角形的次数



怎么算?
 
1) 第n个加泰罗尼亚数字的公式:



2)
•让我们有一个长度为 2n 的 PSS
•显然它以左大括号开头
•所以,假设 P = (A)B,其中 A 和 B –还有psp(另外,A和B可以为空)
•如果A的长度=2k,那么序列A可以用Ck种方式组合
•那么B的长度=2(n – k - 1),B可以用Cn-k-1种方式组合

Problem

输出第 N 个加泰罗尼亚语

输入
输入的第一行包含一个数字N (\(1 <= N <= 20\)) .
 
输出
打印一个数字 - N加泰罗尼亚语
 

 

例子
<头> <日># <正文>
输入 输出
1 1 1