Counting powers of words in monoids.
type: Item
instance of: scholarly article
title: Counting powers of words in monoids.
zbMATH Open document ID: 1187.20064
author: Stephen P. Humphries
author: Zane Kun Li
published in: European Journal of Combinatorics
publication date: 2009-06-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 5565576
zbMATH Keywords: monoids
zbMATH Keywords: powers of words
zbMATH Keywords: combinatorial problems
zbMATH Keywords: Cayley graphs
reviewed by: F. Blanchet-Sadri
describes a project that uses: Magma
describes a project that uses: OEIS
MaRDI profile type: Publication
full work available at URL: j.ejc.2008.10.005
OpenAlex ID: W2002055213
cites work: COUNTING FUNDAMENTAL PATHS IN CERTAIN GARSIDE SEMIGROUPS
cites work: Q4051320
cites work: The On-Line Encyclopedia of Integer Sequences
cites work: Q4003861
DOI: 10.1016/J.EJC.2008.10.005
description: scientific article; zbMATH DE number 5565576