7
$\begingroup$

How many bit strings of length 10 contain at least three 1s and at least three 0s?

$\endgroup$
15
$\begingroup$

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}. $$

$\endgroup$
1
  • 1
    $\begingroup$ Your answer totally makes sense. Now 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. $\endgroup$ – Robert May 31 '11 at 20:17
3
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Hint: The number of $0$s is between (this) and (that); how many strings of length $n$ contain exactly $k$ zeroes?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.