I've got a discrete math problem on my hands...I'm trying to understand the steps behind working with bit strings; specifically, how a bit string of x length has "at least" or "exactly" a certain number of ones or zeros. I understand that it likely uses combinations or permutations, but I'm not sure how to account for that with bit strings.

Thanks in advance!

  • $\begingroup$ You need to be more specific in your question. A bit string is just a string of $0$'s and $1$'s, often of a given length. You might wonder, for example, how many five bit strings have at least four $1$'s. You might wonder how many have a run of (exactly or at least) three $1$'s in a row. Both of these are small enough you can count by hand. You have to read the question carefully. $\endgroup$ – Ross Millikan Apr 10 '13 at 0:07

I'm going to assume the problem you're looking at is something like, "If you have bit strings of length $n$, how many of those have at least $m$ ones? How many have exactly $m$ ones?" (the equivalent question for zeroes is identical).

For the "at least": select $m$ bits of the $n$ total that must be ones (that's $\binom{n}{m}$). There are $2^{n-m}$ ways to assign the rest of the bits, for a total of $\binom{n}{m}e^{n-m}$ strings.

The "exactly": as before choose $m$ bits that must be $1$, i.e. $\binom{n}{m}$. The rest must all be zeroes so you're done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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