# How do I find “at most” x bit strings of length 20?

I tried searching online and I found several examples of doing such problems, but I'm still not sure if I'm doing them correctly and would greatly appreciate some help!

How many bit strings of length 20 have:

a.) exactly four 1's

b.) at most four 1's

C.) at least four 1's

Like I said I've found similar problems but I get different solutions when applying them with my specifics. I think I may have gotten a and b, but not sure about c. Did I do them correctly? Thanks!

• Your expressions for a) and b) are right. (I have not checked the arithmetic.) For c), We could find $\sum_4^{20} \binom{20}{i}$. But it is far easier to say that the total number bit strings is $2^{20}$, and the number of bit strings with $\le 3$ $1$'s is $\sum_0^3\binom{20}{i}$. Then subtract. – André Nicolas Mar 4 '14 at 16:47

To get exactly $k$ ones out of $n$, you are free to select the $k$ positions for the ones, thus $\binom{n}{k}$. To have at most 4 ones is having none, one, two, three, or four.

Some problems are easier to turn around, to have at least 16 ones in 20 is having at most 4 zeros in 20.

Some problems are easy to solve by symmetry, i.e. the average number of ones in all strings of length 20 is the average number of zeros, and so it must be 10.

• Wait what? So I did them wrong? – Cozen Mar 4 '14 at 14:33