1
$\begingroup$

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring.

Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did h(2) manually I got 14 and when I plugged in the value in the equation I also got 14. Now the problem is when I try to do h(3) manually I get 33 and when I plug it in the equation I get 48. What am I doing wrong?

$\endgroup$
  • $\begingroup$ What do the funny lines mean? $\endgroup$ – mvw Feb 10 '16 at 2:46
  • $\begingroup$ It is just something that helps me visualize. The final answer I got from doing that was $$ h(n)=4h(n−1)−2h(n−2)$$ $\endgroup$ – Jason Thapa Feb 10 '16 at 2:51
2
$\begingroup$

I get $49$ of length $3$ by hand count. There are $11$ strings ending in $0$ because we subtract $x20$ and $200$. There are $14$ strings ending in each of $1$ or $3$ because to fail the first two characters must be $12$ or $20$. There are $10$ strings ending in $2$ because we subtract $x12, 122, 202$

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)$$

$$\begin {array} {r | r | r | r | r| r} n&d&e&f&g&h\\ \hline 0&0&0&0&0&1\\1&1&1&1&1&4\\2&3&4&3&4&14\\3&11&14&10&14&49\\4&39&49&35&49&172\\5&137&172&123&172&604\\6&481&604&432&604&2121\\7&1689&2121&1517&2121&7448\\8&5931&7448&5327&7448&26154\\9&20827&26154&18706&26154&91841\\10&73135&91841&65687&91841&322504\\11&256817&322504&230663&322504&1132488\\12&901825&1132488&809984&1132488&3976785\\13&3166801&3976785&2844297&3976785&13964668\\14&11120371&13964668&9987883&13964668&49037590 \end {array}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.