Combinatorics on words

Definition

Let $A$ be a finite set, the alphabet, whose elements are letters. A finite word over $A$ is a finite sequence $w = a_1 a_2 \cdots a_n$ of letters, also called a string; an infinite word is a sequence $(a_i)_{i \ge 1}$ . The finite words form the free monoid $A^*$ under concatenation, with the empty word as identity. A factor of $w$ is a word $u$ with $w = x u y$ for some words $x, y$ . Combinatorics on words is the branch of combinatorics that studies the structure of words in $A^*$ and of infinite words over $A$ . Its typical questions concern factors, repetitions, periods and morphisms of $A^*$ .

Remarks

Example: a square is a nonempty word of the form $u u$ . Every binary word of length at least $4$ contains a square factor. Indeed, a square-free binary word cannot contain $aa$ or $bb$ , so it alternates, and $abab$ or $baba$ is a square.

Example: the Thue–Morse sequence is an infinite binary word with no factor of the form $a x a x a$ with $a$ a letter, so it is overlap-free.

Non-example: the word $ac$ is not a factor of $abc$ . It is only a subsequence of $abc$ , since a factor must consist of consecutive letters.

Results of the field include the Fine–Wilf theorem on words with two periods and the existence of infinite square-free words over three letters.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Binary operation definition
Combinatorics concept
Associativity definition
Identity element definition
Semigroup definition
Monoid definition
Combinatorics on words definition

Tag	`N815PEPPFA`
URI	`m2://N815PEPPFA`
Kind	definition
Writing	W0 stub
MSC	68R15, 05A05
Defines	Combinatorics on words
Uses	Monoid, Combinatorics
Changed	2 November 2026

Combinatorics on words

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here