求状态数

mahuan1279

已知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)=?

zzyong00

n=2时，为什么不是(1,1,-1) 呢？

mahuan1279

zzyong00 发表于 2020-5-22 13:37
n=2时，为什么不是(1,1,-1) 呢？

每个序列由n个1和n个-1组成。

mahuan1279

经群友提醒，可以看成括号配对问题（这个就很好理解了），实质就是卡特兰数。