I need to learn approach to solve following problem, I need this for programming problem.
For a given set of alphabet letters $S$, and pairs of rule and find the number of ways in which $N$ length different strings can be formed.
$\underline{Examples}:$
Given a set of letters $S=\{a, b, c\}$, we have replacement rules $(current\_letter, next\_ letter)$ as below:
$$
\{
(a, a),
(a, b),
(a, c),
(b, a),
(b, c),
(c, a),
(c, b)
\}
$$
How to calculate the number of ways that $N$ length string can be formed such that two consecutive pairs always appears in replacement rules.
For $N = 1$, we have 3 ways either { "$a$", "$b$", "$c$" }
For $N=2$, we have 7 ways { "$aa$"
"$ab$",
"$ac$",
"$ba$",
"$bc$",
"$ca$",
"$cb$" }
For $N=3$, we have 17 ways { "$aaa$",
"$aab$",
"$aac$",
"$aba$",
"$abc$",
"$aca$",
"$acb$",
"$baa$",
"$bab$",
"$bac$",
"$bca$",
"$bcb$",
"$caa$",
"$cab$",
"$cac$",
"$cba$",
"$cbc$" }
Please give me hint, what should I read to sovle this?
Best Answer
Not a complete answer, but especially because you need it for programming I think it might be useful.
For $n=1,2,\dots$ let $A_n,B_n,C_n$ denote the number of stringths having length $n$ that end on $a,b,c$ respectively, and let $T_n$ denote the number of stringth having length $n$.
Then $A_1=B_1=C_1=1$ and: