Discrete Mathematics

Question

consider a bit string of length 10 containing only o and 1. The number of string contain 3 consecutive 0's or 3 consecutive 1's are______

Answer 1

The negation of the above statement is strings containing <=2 consecutive 0's and <=2 consecutive 1's

Let,

T(n) = strings starting with 0 or 00

X(n) = strings starting with 1 or 11

 

Thus,

T(n) = starts with 0 * X(n-1)   + starts with 00 * X(n-2)

X(n) = starts with 1 * T(n-1)   + starts with 11 * T(n-2)

 

Adding both will give the strings containing <=2 consecutive 0's and <=2 consecutive 1's.

 

Thus, to get answer, substract the abov number.