Counting powers of words in monoids. (Q1024329)

Let \(F\) be the free monoid generated by \(a_1,\dots,a_r\), and let \(1\) denote its identity. Also let \(M\) be a monoid with presentation \(M=\langle a_1,\dots,a_r\mid w_1=w_2,\;w_3=w_4,\dots,w_{2s-1}=w_{2s}\rangle\) where every \(w_i\) is distinct from \(1\). Write \(u\equiv v\), if we can get from word \(u\) to word \(v\) by repeatedly replacing occurrences of \(w_{2i-1}\) with \(w_{2i}\) (or vice versa) for some \(i\). In this paper, the authors consider the problem of counting the number \(\delta_{M,w_1}(n)\) of words \(w'\in F\) such that \(w'\equiv w_1^n\), where \(n\in\mathbb{N}\). Here \(\delta_{M,w_1}(n)\) represents the number of paths, from \(1\in M\) to \(w_1^n\), in the Cayley graph of \(M\). As a result, they obtain many interesting sequences including the Fibonacci one.