Number of ways generating $N$ length strings?

Question

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?

Answer 1

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:

• $T_n=A_n+B_n+C_n$
• $A_{n+1}=T_n$
• $B_{n+1}=A_n+C_n$
• $C_{n+1}=A_n+B_n$

Answer 2

This is equivalent to counting the number of paths of length $N-1$ in a directed graph whose vertices are letters, and where there is an edge from $v$ to $w$ if and only if $(v,w)$ is a rule. Letting $A$ be the adjacency matrix of this graph, where $A_{i,j}=1$ if there is an edge from $i$ to $j$ and $A_{i,j}=0$ if not, it is well known that the $(i,j)$ entry of $A^k$ gives the number of directed paths of length exactly $k$ from $i$ to $j$. Therefore, to compute the number of all paths, you just need to add up all the entries in the matrix exponent $A^{N-1}$. This can be computed in $|S|^3\log N$ time using exponentiation by squaring.