Ask Question and Get Free Answers - JUST Ask And Answer > QA > Science & Mathematics > Mathematics
Probability CHALLENGE question?

Answers:1   |   LastAnswerAt:2010.10  

Question
visitor
Dr D 
Asked at 2010.10.12 23:55:25
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).
answer Helmut  Answered at 2010.10.12 23:55:25
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.
1
  • Answer This Question:Probability CHALLENGE question? 

  • insert image

    image url:

    such as: http://www.justaaa.com/**/**.jpg

    insert video

    vedio url: