string - 二元序列相加组合

Question

给定一个序列 a1a2....a_{m+n}与 n +1 和 m -1s，如果有 1=< i <=m+n ， 我们有 sum(ai) >=0 ，即，

a1 >= 0
a1+a2>=0
a1+a2+a3>=0
...
a1+a2+...+a_{m+n}>=0

则满足要求的序列数为C(m+n,n) - C(m+n,n-1) ，其中第一项是序列总数，第二项是指那些子和<0。

我想知道双边序号是否有类似的公式:

a1 >= 0
a1+a2>=0
a1+a2+a3>=0
...
a1+a2+...+a_{m+n}>=0 
a_{m+n}>=0
a_{m+n-1}+a_{m+n}>=0
...
a1+a2+...+a_{m+n}>=0 

我觉得它可以与单边求和问题类似地推导出来，但是数字C(m+n,n) - 2 * C(m+n,n-1)绝对不正确。有什么想法吗？

Answer 1

线索:第一种情况是从 (0,0) 到 (n+m, n-m) 点的多条路径(步长为 +-1)，其中路径永远不会低于零线。 (类似于括号对的加泰罗尼亚数字，但没有平衡要求 n=2m)
所需的公式是从不超过 (n-m) 线的 (+-1) 条路径。可以得到递归公式。我希望它存在紧凑的公式。

如果我们考虑 nxm 网格的格子路径，其中水平步长为 +1，垂直步长为 -1，那么我们需要许多路径由具有 (n-m) 底的平行四边形限制