求状态数

_only

已知n个1和n个-1组成一个序列，要求序列满足以下规则：
1、第一项必须为1；
2、最后一项必须为-1；
3、从第一项开始，任意1~K(1<=K<=N)项的和不能小于0.
求满足以上三条规则的序列的总个数。


显然，n=1时有（1，-1），即满足要求的序列个数为1；
n=2时有（1，1，-1，-1）和（1，-1，1，-1），即满足要求的序列个数为2；
……
f(n)=?

obibohazek

一网友提醒，看成左右括号配对问题，那就是卡特兰数了。

icakeekohude

用2进制表示可能简单些。
已知 n 个 1 和 n 个 0 组成一个序列，要求序列满足以下规则：
1、第一项必须为 1；
2、最后一项必须为 0；
3、从第一项开始，任意 1~K(1<=K<=N) 项的和不能小于 1.
求满足以上三条规则的序列的总个数。
干脆：n个1和n个0组成一个序列，要求任意项的和不能小于1.