Question

Let S be the set of strings on the alphabet { 0 , 1 , 2 , 3 } that do not contain 12 or 20 as a substring. Give a recursion for the number h ( n ) of strings in S of length n. Hint: Check your recursion by manually computing h(1), h(2), h(3), and h(4).

Answer 1

Answer:

h(n) = 4h(n - 1) -2h(n - 2) + h(n - 3)

Step-by-step explanation:

Let d(n) be the number of good n character strings ending in 0

Let e(n) be the number of good n character strings ending in 1

Let f(n) be the number of good n character strings ending in 2

Let g(n) be the number of good n character strings ending in 3

h(n) = d(n) + e(n) + f(n) + g(n)

e(n) = g(n) = h(n - 1)

f(n) = d(n - 1) + f(n - 1) + g(n - 1)

d(n) = d(n - 1) + e(n - 1) + g(n - 1)

f(n) = h(n - 1) - e(n - 1) = h(n - 1) - h(n - 2)

d(n) = h(n - 1) - f(n - 1) = h(n - 1) - h(n - 2) + h(n - 3)

h(n) = 4h(n - 1) -2h(n - 2) + h(n - 3)

Checking recursion manually,

when h(1) ⇒ d(1) = 1,     e(1) = 1,       f(1) = 1,    g(1) = 1,       h(1) = 4

         h(2) ⇒ d(2) = 3,   e(2) = 4,    f(2) = 3,    g(2) = 4,    h(2) = 14

         h(3) ⇒ d(3) = 11,   e(3) = 14,   f(3) = 10,   g(3) = 14,   h(3) = 49

         h(4) ⇒ d(4) = 39,  e(4) = 49,  f(4) = 35,  g(4) = 49,  h(4) = 172

Note:

Sum of the four values gives "h(n)

Since e(n) = g(n), the values are the same