Probability CHALLENGE question?

Question

A binary string of 2n digits consists of n 0s (zeros) and n 1s (ones). A successful string is one where at any digit position, the number of ones (counting from the left) does not exceed the number of zeros.

eg for n = 3
001101 is a successful string.
011001 is not, since after 3 digits, there are more ones than zeros.

If the string is randomly generated from n 0s and n 1s, show that the probability of generating a successful string is 1/(n+1).

Just in case you're wondering where I got that question, I just stumbled upon it while working on another question.

http://answers.yahoo.com/question/index?qid=20070608125732AAkLUHV&r=w#NbUvWjS6VjUPI10CkR0I

For 2n = 6, these are the only 5 successful strings:
000111
001011
001101
010011
010101

Total possible strings = 6! / (3!)^2 = 20
So prob = 5/20 = 1/(3+1)
The formula works. The question is how to prove it.

Answer 1

call p(n) the probability of success given n digits.
p(1) = (2^2 - 2)/2^2 = 2/4
p(2) = (2^3 - 2)/2^4 = 6/16
p(3) = (2^4 - 2 + 2^3 - 2)/2^6 = 20/64
p(4) = (2^5 - 2 + 2(2^4 - 2 + 2^3 - 2)/2^8 = 70/256
p(5) = ((2^6 - 2) + 3(2^5 - 2) + 5((2^4 - 2) + (2^3 - 2)))/2^10 = 252/1024
p(6) = ((2^7 - 2) + 4(2^6 - 2) + 9(2^5 - 2) + 14((2^4 - 2) + (2^3 - 2)))/2^12 = 924/4096
which definitely does not resolve to 1/(n + 1)
edit:
I sit corrected & red-eared!
After finally reading the problem, I came up with this pattern:
n(1) = 1
n(2) = 1 + 1 = 2
n(3) = 1 + 2 + 2 = 5
n(4) = 1 + 3 + 5 + 5 = 14
n(5) = 1 + 4 + 9 + 14 + 14 = 42
n(6) = 1 + 5 + 14 + 28 + 42 + 42 = 132
n(7) = 1 + 6 + 20 + 48 + 90 + 132 + 132 = 429
n(8) = 1 + 7 + 27 + 75 + 165 + 297 + 429 + 429 = 1430
n(9) = 1 + 8 + 35 + 110 + 275 + 572 + 1001 + 1430 + 1430 = 4862
n(10) = 1 + 9 + 44 + 154 + 429 + 1001 + 2002 + 3432 + 4862 + 4862 = 16796
n(11) = 1 + 10 + 54 + 208 + 637 + 1638 + 3640 + 7072 + 11934 + 16796 + 16796 = 58786
n(12) = 1 + 11 + 65 + 273 + 910 + 2548 + 6188 + 13260 + 25194 + 41990 + 58786 + 58786 = 208012
n(13) = 1 + 12 + 77 + 350 + 1260 + 3808 + 9996 + 23256 + 48450 + 90440 + 149226 + 208012 + 208012 = 742900
n(14) = 1 + 13 + 90 + 440 + 1700 + 5508 + 15504 + 38760 + 87210 + 177650 + 326876 + 534888 + 742900 + 742900 = 2674440
n(15) = 1 + 14 + 104 + 544 + 2244 + 7752 + 23256 + 62016 + 149226 + 326876 + 653752 + 1188640 + 1931540 + 2674440 + 2674440 = 9694845
n(16) = 1 + 15 + 119 + 663 + 2907 + 10659 + 33915 + 95931 + 245157 + 572033 + 1225785 + 2414425 + 4345965 + 7020405 + 9694845 + 9694845 = 35357670
n(16) = 1 + 16 + 135 + 798 + 3705 + 14364 + 48279 + 144210 + 389367 + 961400 + 2187185 + 4601610 + 8947575 + 15967980 + 25662825 + 35357670 + 35357670 = 129644790
n(17) = 1 + 17 + 152 + 950 + 4655 + 19019 + 67298 + 211508 + 600875 + 1562275 + 3749460 + 8351070 + 17298645 + 33266625 + 58929450 + 94287120 + 129644790 + 129644790 = 477638700
n(18) = 1 + 18 + 170 + 1120 + 5775 + 24794 + 92092 + 303600 + 904475 + 2466750 + 6216210 + 14567280 + 31865925 + 65132550 + 124062000 + 218349120 + 347993910 + 477638700 + 477638700
Proving that (n + 1)N(n) = ((2n)Cn) depends on finding a general expression for N(n) in a product form, or converting ((2n)Cn) from product to sum.

Answer 2

I made some progress, but it's going to take some time to finish. I'll go ahead and write out what I've done, and if someone else wants to take it from there, that's great.

first the easy part. the total number of possible strings with n 0's and n 1's is (2n)!/n!n!. so we just need to count the number of successful strings and divide by this number.

one way to "generate" successful strings is to start with the string 010101...., and then if you wish you can move 0's to the left. ALL the successful strings may be generated in this way.

for example, for n=3 we start with 010101. the first 0 can't move to the left, so we look at the 2nd 0. you can move it left if you want, to get 001101, or you can just leave it alone. if you left it alone, then the third 0 can either be moved left to get 010011, or it can be left alone. however, if you moved the second 0, then there are 3 choices for the 3rd 0: leave it alone, move it one place to get 001011, or move it 2 places to get 000111. altogether, there are 5 successful strings in this case.

in general, you can summarize these movements of 0's by a sequence of numbers (p_1, p_2,...., p_{n-1}) such that
0 ≥ p_1 - 1 ≥ p_2 - 2 ≥ .... ≥ p_{n-1} - (n-1). so now the question is how to count the number of such sequences. the tricky part is that, while there are always 2 possibilities for p_1, the number of possibilities for p_2 depends on what p_1 is.

Answer 3

♥ no Helmut, Dr.D is right! I’ve composed a PC program and checked it up to n=12; but I’m brain constipated to prove it formally!

Answer 4

1-65

Answer 5

anumber between 1 and 65