---
tag: YJ961M051W
kind: concept
name: Combinatorics on words
msc: [68R15, 05A05]
specializes: [0JKW7W7XFR]
sources:
  - url: https://en.wikipedia.org/wiki/Combinatorics_on_words
same_as:
  wikidata: Q2985058
  wikipedia: Combinatorics on words
---

## Summary

Combinatorics on words studies finite and infinite sequences of letters from an alphabet, see the [[definition|N815PEPPFA]].
Typical topics are repetitions such as squares and overlaps, periodicity, unavoidable patterns, and the number of distinct factors of a word.
Classical objects of the field are the [[Thue–Morse sequence|7JZVT385PC]] and the [[de Bruijn sequences|GY8F3M39R8]].
It has links with algebra through the free [[monoid|0N6R902FG1]] of words, with number theory, and with the theory of formal languages.

## Explanations

### L1 human

A word is just a string of letters, such as $abaab$.
Combinatorics on words asks which patterns must appear in long words and which can be avoided.
For example, every word of length $4$ on two letters contains a block repeated twice in a row, such as $aa$ or $abab$.
On three letters, by contrast, there are infinite words with no such repeated block.