Question

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?
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.

Answer 1

where u got stuck... ?

Answer 2

1; 2, and 3 equal to 101 : \(2^{12}\) strings
+
12; 13; 14, and 15 equal to 1001 : \(2^{11}\)
+
3; 4; 5, and 6 equal to 1010 : \(2^{11}\)
-
1; 2, and 3 equal to 101 AND 3; 4; 5, and 6 equal to 1010 : \(2^8\)

Answer 3

I'm not sure that this response is correct...the first three are, but the last subtraction, shouldn't it be -(2^10) ??

Answer 4

hmm for the last subtraction, we are fixing 6 bits. so permutations are 2^9. sorry it was a typo i guess

Answer 5

Can you explain s^9 some, does it matter that 3 is in two of the required subsets?

Answer 6

sorry, 2^9, not s^9

Answer 7

we just used n(a+b) = n(a) + n(b) - n(a&b)

below two have intersection elements. so simply add both and subtract the interesection.
1; 2, and 3 equal to 101
3; 4; 5, and 6 equal to 1010

we are fixing the positions : 1,2,3,4,5,6
so rest of the the positions 9 can be permuted in 2^9 ways

Answer 8

and may i ask how did u get 2^10

Answer 9

sorry, looks like bad math there on my part...one more question, I agree with 2^9 for the subset 1,2,3,4,5,6, but should we also account for the subset 12,13,14,15, thus making the final subtraction 2^5?

Answer 10

why no it is disjoint right so nothing to subtract eh ?

Answer 11

I guess i don't understand what you mean...

Answer 12

Aren't we accounting for the fixing of 10 positions, 1,2,3,4,5,6,12,13,14,15?

Answer 13

okay.

if the question doesnt have the 3rd constraint. and only asks this :
1; 2, and 3 equal to 101, or have bits 12; 13; 14, and 15 equal to 1001 or have bits

can you tell the number of permutations ?

Answer 14

there are three constraints which are subsets, right?

Answer 15

2^12 + 2^11 - 2^8
if we are only considering the first two constraints

Answer 16

may i know why u subtracting 2^8

Answer 17

those are the fixed positions 1,2,3,12,13,14,15

Answer 18

the question is a "either this or that satisfying" type not "all satisfying" type.

First constraint : 1; 2, and 3
Second constraint : 12; 13; 14, and 15

are there any common positions ?

no.

so the number of permutations are simply
2^12 + 2^11

Answer 19

dang, see it now...let's continue

Answer 20

great :)

so we subtract only when there is some overlap