二進制序列子求和組合

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 

我覺得它可以派生類似的單邊subsum問題，但號碼C(m+n,n) - 2 * C(m+n,n-1)肯定是不正確的。有任何想法嗎 ？

Answer 1

甲線索：第一種情況是從（0,0）一數量的路徑（用+ -1步驟）到（N + M，N-M）的點，其中路徑從來沒有低於零線。 （像Catalan數爲括號對，但沒有平衡要求N = 2M）
所需的式是一個數字的（+ -1）路徑從未上述上升（N-M）線。有可能得到遞歸公式。我希望它有一個緊湊的公式。

如果我們考慮晶格路徑在n×m個柵格，其中對於1水平臺階和垂直步驟，用於-1，那麼我們需要一些由parallelogramm與（nm）的基