Question

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

Answer 1

How many strings of length 4 can be generated from the letters {A,B,C,D} ?

$$4^4=256$$

If the element $AB$ is on the first place

$$4^2=16$$

If the element $AB$ is on the second place

$$4^2=16$$

If the element $AB$ is on the third place

$$4^2=16$$

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

$$256-(16+16+16)=208$$