How many bit strings of length 10 contain at least three 1s and at least three 0s?
A simple "number of bit strings", so I thought
4 Answers
Let's think about just placing the 0's and let the 1's fill in the remaining spots. The cases we are interested in are how to get exactly 3, 4, 5, 6, and 7 0's.
How many strings have exactly 3 0's? This is just the number of ways to choose 3 locations out of 10 available locations where order doesn't matter, which is $\binom{10}{3}$. Remember, we're only focusing on the 0's - the 1's just fill in the remaining spots.
The argument is the same for getting exactly 4, 5, 6, and 7 0's. To get the total, we just add them all up:
$ \binom{10}{3} + \binom{10}{4} + \binom{10}{5} + \binom{10}{6} + \binom{10}{7}. $
-
1Your answer totally makes sense. $N$ow I know why I was undercounting in my attempt. It seems for the at-least type of questions, a good approach to solve them is to use a systematic method as exemplified by yours to ensure correctness. Rushing to solve by a shortcut, especially in a test, probably will result in an incorrect answer. Thank you a bunch. – 2011-05-31
Consider the complementary problem: at most 2 0s or at most 2 1s. The counts for each case is $\binom{10}{2}+\binom{10}{1}+\binom{10}{0}=56$; the count for at least 3 0s and at least 3 1s is therefore $2^{10}-2\cdot 56=912$
As we will have 10 places total so this problem will get reduced to 10 places consisting of 7 zeros and 3 ones ,6ones and 4 zeroes, 5 ones and 5 zeroes. so $(2\cdot\frac{10!}{7!\cdot 3!})$ (one for 7 zeroes and 3 ones and other case is 3 ones and 7 zeroes)+$2\cdot \frac{(10!}{6!\cdot4!})$ (one case 6 ones and 4 zeroes and other vice versa)+ $\frac{10!}{5!\cdot 5!}$
so Total answer is 912
Hint: The number of $0$s is between (this) and (that); how many strings of length $n$ contain exactly $k$ zeroes?