This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the sequence "102". The answer to that problem was $a_n = 3a_{n-1} - a_{n-3}$. In this question however , the forbidden sequence "cab" must appear at the beginning of the string, and nowhere else.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let this recurrence relation be $b_n$. We have that $b_n = a_{n-3}$, as we simply add "cab" at the beginning and it doesn't affect anything else.
Thus, similarly, $b_n=3b_{n-1}-b_{n-3}$ as we have $a_{n-3} = 3a_{n-4}-a_{n-6}$.
For example, for the non $cab$ strings of length $3$, we have:
$$abc,acb,bac,bca,cba$$
And thus for the non $cab$ strings that must start with $cab$ we have:
$$cababc,cabacb,cabbac,cabbca,cabcba$$
