Enumerative combinatorics on words

Dominique Perrin (1) , Antonio Restivo (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Matematica e Applicazioni [Palermo]

Combinatorics on words is a field which has both historical roots and a substantial growth. Its roots are to be found in the early results of Axel Thue on square free words and the development of combinatorial group theory. The present interest in the field is pushed by its links with several connexions with other topics external to pure mathematics, notably bioinformatics. Enumerative combinatorics on words is itself a branch of enumerative combinatorics, centered on the simplest structure constructor since words are the same as finite sequences. In this chapter, we have tried to cover a variety of aspects of enumerative combinatorics on words. We have focused on the problems of enumeration connected with conjugacy classes. This includes many interesting combinatorial aspects of words like Lyndon words and de Bruijn cycles. One of the highlights of the chapter is the connexion between both of these concepts via the theorem of Fredericksen and Maiorana.

Domaines: Théorie et langage formel [cs.FL]; Combinatoire [math.CO]

Dominique Perrin, Antonio Restivo. Enumerative combinatorics on words. Miklos Bona. Handbook of Enumerative Combinatorics, CRC Press, 2015, 9781482220858. ⟨hal-01121901⟩