Hello,I would like to get some help with following brainteaser:Suppose there are fifty "1" and fifty "-1".How many way this sequence of 100 numbers can be constructed such that the subtotal is always >= 0?For example:In case of 2 numbers, there is only 1 way:1, -1In case of 4 numbers, there are 2 ways:1, 1, -1, -11, -1, 1 , -1In case of 6 numbers, there are 5 ways:1, 1, 1, -1, -1, -11, 1, -1, 1, -1, -11, 1, -1, -1, 1, -11, -1, 1, -1, 1, -11, -1, 1, 1, -1, -1In case of 8 numbers, there are 14 ways (if my calculation is correct.)But I could find a pattern to generalize it. Please help.Thank you very much.Peter

If you note f(i) the number of such sequences where i is the number of "+1" and f(0)=1, you have the following:f(n)=Sum (j=0 to n-1) f(j)*f(n-1-j)for i=50, the result is close to 2*10^27

I don't think that's correct.For i = 50, there are total of about 10^15 combination. Number of sequences such that the subtotal is always >= 0 should be much smaller. 50!------------ = 126,410,606,437,752 (about 10^15)25! * 25!

Check catalan numbers. They are exactly what you are looking for. http://en.wikipedia.org/wiki/Catalan_numberThe answer is C(49)=98!/(50!49!)

Awesome, thank you very much.After reading through the wiki page, since n start from 0, I think the correctly answer for 100 numbers should be: 100!-------------- = 1,978,261,657,756,160,653,623,774,456 51! * 50! where n = 50.