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.


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?

  • 2
    $\begingroup$ The rules prohibit having consecutive $b$s or consecutive $c$s. Have you tried to construct a recurrence relation? $\endgroup$ Jun 4, 2019 at 9:06

2 Answers 2


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$
  • $\begingroup$ Thanks, I will explore on it further $\endgroup$ Jun 4, 2019 at 9:18
  • $\begingroup$ You welcome. Good luck. $\endgroup$
    – drhab
    Jun 4, 2019 at 9:19
  • $\begingroup$ helped me very much. Thanks $\endgroup$ Jun 6, 2019 at 9:41

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.

  • $\begingroup$ Thanks for the answer, I draw the execution tree by hand (like I drawn in linked answer) It was tree for me instead ... indeed I am looking for an efficient solution --- my current implement ion not good when $N > 1000000$ $\endgroup$ Jun 6, 2019 at 9:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .