Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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

share|improve this answer
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. –  Robert May 31 '11 at 20:17

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

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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