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!
Best Answer
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.