# Thread: Number of Valid Lists in a Combination

1. ## Number of Valid Lists in a Combination

Originally Posted by Puzzle
Seven numbers, each 1 or -1, are listed in a row in such a way that adding the numbers successively from left to right never gives a negative answer. For example, 1 -1 1 1 -1 -1 1 has successive sums 1, 0, 1, 2, 1, 0, 1 and is valid, while 1 1 -1 -1 -1 1 1 has successive sums 1, 2, 1, 0, -1, 0, 1, and is not valid. How many valid lists are there?
Well, it's more of help I'm seeking for rather than providing a puzzle to be solved (but who knows, maybe it'll be enjoyable for you to help solve it? :3).

Anyway, I worked out that there are three combinations that would result in a positive answer (i.e. > 0), irrespective of position. Then for each possible combination I worked out how many variations in positioning there would be, as shown below:

So in total, there are 18 possible combinations (7+6+5). Is this answer correct?

EDIT: I'm an idiot, lol =.=

2. ## Re: Number of Valid Lists in a Combination

Clearly, the first number is 1 and there can be at most three -1's in the sequences. There are $\displaystyle \binom{7}{0} + \binom{7}{1} + \binom{7}{2} + \binom{7}{3} = 64$ possible sequences with at most three -1's. We count the number of invalid sequences of at most three -1's and subtract from 64. Invalid sequences can occur in one of these cases:

Case 1: 1,-1,-1,...

Case 2: 1,1,-1,-1,-1,...

Case 3: 1,-1,1,-1,-1,...

Case 1 can occur in 16 ways, and cases 2 and 3 can occur in 4 ways each (no overlap), and 16+4+4 = 24. Hence the answer is 64-24 = 40.