How many bit strings of length 15 have bits 1, 2, 3 equal to 101, or have bits 12, 13, 14, 15 equal to 1001 or have bits 3, 4, 5

Question

lakkis [162]

3 years ago

10

How many bit strings of length 15 have bits 1, 2, 3 equal to 101, or have bits 12, 13, 14, 15 equal to 1001 or have bits 3, 4, 5

, 6 equal to 1010?

Mathematics

1 answer:

lesya [120] · Answer 1 · 2022-04-22T15:43:51+03:00

This is an excellent practice on the law of inclusion/exclusion.
For example, using | | to represent cardinality (i.e. count in the set)
|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|.
I am not allowed to provide a link, but if you could use some additional reading, google "wiki Inclusion–exclusion_principle" and the first wiki entry should explain that in more detail.

Here we have
A=the set of 15bit numbers starting with 101xxxx...
B=the set of 15bit numbers starting with xx1010xxxx...
C=the set of 15bit numbers ending with xxxxxxxxxxx1001
A∩B=101010xxxxx
B∩C=101xxxxx...xxx1001
C∩A=xx1010xx...xxx1001
A∩B∩C=101010xxxxx1001

Therefore
|A|=2^12 (there are 12 bits left)
|B|=2^11 (there are 11 bits left)
|C|=2^11 (there are 11 bits left)
|A∩B|=2^9 (9 bits left)
|B∩C|=2^8 (8 bits left)
|C∩A|=2^7 (7 bits left)
|A∩B∩C|=2^5 (5 bits left)

Applying the inclusion/exclusion principle,
|A∪B∪C|
=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|
=2^12+2^11+2^11-2^9-2^8-2^7+2^5
=7328