# Number of ways generating $N$ length strings?

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$$" }

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

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

• 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$ Jun 6, 2019 at 9:46