I am doing practice problems for an exam and I was wondering for this question if I am correct.
How many bit strings of length 7 contain (a) exactly three 1s? (b) at most three 1’s? (c) at least three 1’s?
(a) for part a because there is repetition and order of the positions for the 3 ones doesnt matter I would do C(7,3). There can only be 1's left.
(b) I would take the total number of permutations and subtract the cases where 4 or more 1's exist 2^7 – 2^3. For this problem I am unsure of because I would have liked to have done 2^7 – C(7,4)*2^3 but that comes out negative. Another way I can see doing this is I take 4 0's so C(7,4)2^3 but this is still greater than the total number of combinations.
(c) I would select three 1's and do C(7,3) * 2^4
Best Answer
The easy thing to calculate is the number with exactly $k$ 1s, namely ${7 \choose k}$. "At most $3$" is $0, 1, 2,$ or $3$, so you could take $${7 \choose 0} + {7 \choose 1} + {7 \choose 2} + {7 \choose 3} = 64$$ "At least $3$" is $3, 4, 5, 6,$ or $7$, so
$${7 \choose 3} + {7 \choose 4} + {7 \choose 5} + {7 \choose 6} + {7 \choose 7} = 99$$ Or, for maybe slightly less computation, you could say "at least 3" means not ($0,1,$ or $2$), so (since there are $2^7$ bit-strings of length $7$ in all) $$ 2^7 - \left({7 \choose 0} + {7 \choose 1} + {7 \choose 2}\right) = 99$$
Of course, if you've already calculated $64$ for "at most $3$" and $35$ for "exactly 3", you can say "less than $3$" is $64 - 35 = 29$ so "at least $3$" is $2^7 - 29 = 99$.