Lesson 4

The same idea works, for example, for words over any finite alphabet with forbidden adjacent pairs. Let the alphabet be \(\Sigma=\{\sigma_{1},\dotsc,\sigma_{k}\}\), and let \(A\) be the \(k \times k\) matrix defined as follows: \[A_{ij}= \begin{cases}1,&\text{if the pair }\sigma_i\sigma_j\text{ is allowed,}\\ 0,&\text{if the pair }\sigma_i\sigma_j\text{ is forbidden.}\end{cases}\] Let \(v_{n}\) be the row vector whose \(i\)-th coordinate is the number of valid words of length \(n\) ending in the letter \(\sigma_{i}\). Then \[v_{n+1}=v_{n}A.\] Since every one-letter word is valid, \(v_{1}=\mathbf{1}^{T}\), where \(\mathbf{1}\) is the column vector of all ones. Thus, the total number of valid words of length \(n\) is \[N(n)=\mathbf{1}^{T}A^{n-1}\mathbf{1}.\]

For example, if \(\Sigma=\{a,b,c\}\) and the forbidden pairs are \(ab\), \(ac\), and \(bb\), then \[A= \begin{pmatrix}1&0&0\\ 1&0&1\\ 1&1&1\end{pmatrix}.\] After that, the problem becomes just a matrix-power computation.