binary sequence subsum combinations

Question

Given a sequence a1a2....a_{m+n} with n +1s and m -1s, if for any 1=< i <=m+n, we have sum(ai) >=0, i.e.,

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

then the number of sequence that meets the requirement is C(m+n,n) - C(m+n,n-1), where the first item is the total number of sequence, and the second term refers to those sub-sum < 0.

I was wondering whether there is a similar formula for the bi-side sequence number :

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

I feel like it can be derived similarly with the single-side subsum problem, but the number C(m+n,n) - 2 * C(m+n,n-1) is definitely incorrect. Any ideas ?

Some sequences are doubly excluded. This question would fit better on the Mathematics Stack Exchange (migration is too slow, so repost there and delete this one). — David Eisenstat
– David Eisenstat, Commented Apr 27, 2014 at 3:08
This question appears to be off-topic because it is about combinatorics, not about programming. — Paul Hankin
– Paul Hankin, Commented Apr 27, 2014 at 10:31

MBo · Accepted Answer · 2014-04-27 06:26:14Z

1

A clue: the first case is a number of paths (with +-1 step) from (0,0) to (n+m, n-m) point, where path never falls below zero line. (Like Catalan numbers for parenthesis pairs, but without balance requirement n=2m) enter image description here
Desired formula is a number of (+-1) paths which never rise above (n-m) line. It is possible to get recursive formulas. I hope that compact formula exists for it.

If we consider lattice path at nxm grid, where horizontal step for +1 and vertical step for -1, then we need a number of paths restricted by parallelogramm with (n-m) base

enter image description here

edited Apr 27, 2014 at 6:26

answered Apr 27, 2014 at 4:01

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

binary sequence subsum combinations

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related