Answer to Question #247660 in Discrete Mathematics for Anirudh

Question

How many strings of length 4 on the alphabet {A,B,C,D} do not contain AB as a substring

Answer 1

N=$4\cdot 4\cdot 4\cdot 4=256$ - number of all strings above {A,B,C,D}

Let we find number of strings with substring "AB"

N1=card({AB**}\{ABAB})=4$\cdot 4$ -1=15;

N2=card({*AB*})=4$\cdot 4$ =16

N3=card({**AB}\{ABAB})=16-1=15;

N4=card({ABAB})=1;

N-=N1+N2+N3+N4=47;

N+=N-(N-)=256-47=209- number of words without "AB"

Answer=209