PLEASE SHOW WORK FOR FULL POINTS. I AM TRYING TO LEARN. Another inclusion-exclus

Question

PLEASE SHOW WORK FOR FULL POINTS.  I AM TRYING TO LEARN.

Another inclusion-exclusion problem:

How many bit strings of length 15 have bits

1; 2, and 3 equal to 101, or have bits 12; 13; 14, and 15 equal to 1001 or have bits

3; 4; 5, and 6 equal to 1010? (Let's count bits left to right so 101000000000000 has

101 for bits 1,2,and 3.)

Hint: The fact that the third bit appears in two of the required patterns means

some special care will be needed to get the count correct.

I need to see all of the steps.

Explanation / Answer

1; 2, and 3 equal to 101 (x)-
other twelve places have 2 possibility for each place
so,
no. of strings = 2^12

12; 13; 14, and 15 equal to 1001(y) -
other eleven places have 2 possibility for each place
so,
no. of strings = 2^11

3; 4; 5, and 6 equal to 1010(z)-
other eleven places have 2 possibility for each place
so,
no. of strings = 2^11


x intersection y = other eight places have 2 possibility for each place
so,
no. of strings = 2^8

x intersection z = other eight places have 2 possibility for each place
so,
no. of strings = 2^8

y intersection z = other seven places have 2 possibility for each place
so,
no. of strings = 2^7



x intersection y intersection z = other four places have 2 possibility for each place
so,
no. of strings = 2^4

so,
lets denote intersection by *
so,
ans is
x + y + z -(x*y + y*z + z*x) + (x*y*z)
= 2^12 + 2^11 + 2^11 -(2^8 + 2^8 + 2^7) + 2^4
= 7568 strings

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.