4
$\begingroup$

I have a problem on my home work for applied discrete math

How many bit strings of length 10 contain

A) exactly 4 1s

the answer in the book is 210

I solve it

$$C(10,4) = \frac{10!}{4!(10-4)!} = 210 $$

for the last 3 though I can't even get close. Did I even do part A right or is the answer only a coincidence?

B) at most 4 1s

the answer in the book is 386

C) at least 4 1s

the answer in the book is 848

D) an equal number of 0s and 1s

the answer in the book is 252

$\endgroup$

3 Answers 3

8
$\begingroup$

Your answer for part (a) is fine. For part (b), we have to ask what does "at most four" mean? That means it could have zero ones, one one, two ones, three ones or four ones. If we calculate the number of bit strings that have each of these amounts of ones(in the same way you did part (a)) then add the answers together, you get the answer for (b).

(C) is similar to (b), but "at least four" means four or more. Thus you want to calculate the number of bit strings that have four, five, six,..., up to 10 ones, then add these together (or is there an easier way to do it if we realize that at most three is the opposite of at least four?)

Then for (D), if we have the same number of zeros and ones, how many ones do we have? If we calculate the number of bit strings that have that many ones, we are done.

$\endgroup$
1
  • 1
    $\begingroup$ For those wondering about "C", the answer is subtraction. $\endgroup$ Mar 10, 2016 at 23:40
5
$\begingroup$

Part (A) is fine.

For part (B), though, ${10\choose 0} + {10\choose 1} + .... +{10\choose 4}$, I get an answer of 386,

so either there is a typo in your post, or the book answer is wrong.

For part (C), you could very well apply a short cut.

Total ways for the string is $2^{10}$, because there are 2 choices for each bit.

["at most 4 1's] - ["exactly 4 1's"] gives [at most 3 1's] = 386 - 210 = 176 ,

and [ at least 4 1's] = $2^{10} - 176 = 848$

$\endgroup$
0
$\begingroup$

For part A it will be simply $C(10,4)=210$

For part B it will be $C(10,0)+C(10,1)+C(10,3)+C(10,4)=386$ because at most means maximum which we actually start from zero till that particular number

For part C it will be simply $C(10,4)+C(10,5)+C(10,6)+C(10,7)+C(10,8)+C(10,9)+C(10,10)=848$

For part D it will be simply $C(10,5)=252$

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