Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given the set of all binary strings of length n, I am looking at the "middle" of these strings, weight-wise.

Namely, I am trying to calculate how many words are there whose weight is between n/2 - sqrt(n) and n/2 + sqrt(n).

Clearly this term can also be described as a sum of binomial coefficients, but I don't know how to simplify it. I am less interested in the exact outcome (Although it would be great if I could get it), and more interested in the asymptotical lower bound. (Is this about Omega(2^n)? Omega(2^sqrt(n))? Something else?)

share|improve this question
    
en.wikipedia.org/wiki/… –  Steve Huntsman Jul 16 '13 at 17:39
    
Follow the link Steve gives. This is not a research level question and is therefore inappropriate for this site. You'll get help at math.stackexchange.com . –  Brendan McKay Jul 16 '13 at 22:55
add comment

closed as off-topic by Brendan McKay, Yemon Choi, Chris Godsil, Andres Caicedo, Theo Johnson-Freyd Jul 17 '13 at 3:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Brendan McKay, Yemon Choi, Chris Godsil, Andres Caicedo, Theo Johnson-Freyd
If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

To spell out the hint a bit more explicitly - the mean number of 1s in a random binary string of length $n$ is $n/2$, and the standard deviation is $\sqrt{n}/2$. So you're looking for the number of such words which have their number of 1s within two standard deviations of the mean.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.