#2449. 递推4-5 Catalan数

递推4-5 Catalan数

题目描述

定义:Cn=n+2条边的多边形,求能被分割成三角形的方案数?

例如5边型的分割方案有:

输入格式

一个整数n

输出格式

分隔成三角形的方案数
5
42

提示

【类似题1】 :n个1和n个0组成一2n位的二进制,要求从左到右扫描,1的累计数不小于0的累计数,试求满足这条件的数有多少?

【类似题2】将n个1和n个-1排成一行,要求第1个数至第k个数的累加和均非负,问有几种排列方法?

【类似题3】有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少种方法使得只要有10元的人买票,售票处就有5元的钞票找零?

【类似题4】一个栈(无穷大)的进栈序列为1,2,3,..n,

有多少个不同的出栈序列?

【类似题5】 :P=A1×A2×A3×……×An,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?