Determine an, the number of words of length n on the alphabet {a, b, c} which
do not contain the substring ab. For instance, a3 = 21 since there are 21 such words
with 3 letters, namely:
aaa aac aca acb acc baa bac
bba bbb bbc bca bcb bcc caa
cac cba cbb cbc cca ccb ccc.
Solution.
There are different words of length over this alphabet {a,b,c}.
1){b.......} or {c........}
If a string begins with b or c, then we are left with a string of length n−1, which can start with any character. There are an-1 strings of this type.
We have strings of this kind.
2) {aa.......} or {ac......}
If a string begins with a, and the second letter must be a or c, then you are left with a string of length n−2, which can start with any character. There are an-2 strings of this type.
We have
strings of this kind.
3) {aab.....}
Subtract the number of lines of this type.
We have strings of this kind.
4) So, we have answer
For a example,
Comments