0

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!

Emily
  • 1
  • 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. – Ross Millikan Apr 10 '13 at 00:07

1 Answers1

1

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.

Julien Clancy
  • 4,868