aimisiyou 发表于 2020-5-22 09:26:42

求状态数

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

aimisiyou 发表于 2020-5-22 10:37:20

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

王守恩 发表于 2020-5-22 12:00:35

本帖最后由 王守恩 于 2020-5-22 12:03 编辑

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