求状态数

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.

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 求状态数

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。