Is a formula for the *number* of Lyndon words of a fixed length over a given number of generators known?

Question

In this paper, P.J. Hilton describes the homotopy type of a wedge of spheres (in terms of the homotopy types of the spheres in that wedge).

Therein, he describes what he defines as basic products. He does this in the context of the matter which he is discussing (homotopy theory), but my question isn't related to that at all. I'll rewrite the definition given there here:

Suppose that we have an "alphabet" of length $k$; $\{a_1,...,a_k\}$ (that is, we have a lexicographic ordering). Basic products are defined inductively as follows:

Basic products of length $1$ are simply the elements $a_1,...,a_k$, and these are ordered according to the lexicographic ordering which we started with. We define basic products of length $n$ inductively. Suppose that basic products of length $<n$ are defined and ordered.

A basic product of length $n$ is a bracket $[a,b]$ satisfying the following:

1. $l(a)$+$l(b) = n$ (where $l(a)$ denotes length $a$),
2. $a<b$ (according to the ordering defined on words of lower length),
3. If $b$ is already such a bracket $[c,d]$, then $c \leq a$.

The basic products of length $n$ are then ordered lexicographically themselves (done by ignoring brackets), and are defined to be strictly greater than any basic product of (strictly) shorter length.

This definition is not the same as the definition of Lyndon words over a particular alphabet, but the number of basic products of length $n$ coincides with the number of Lyndon words of length $n$.

The number of Lyndon words of length $n$ over an alphabet of $2$ elements is given as a sequence here, together with a formula.

Is a formula known for the number of Lyndon words of length $n$ over an alphabet of length $k$, for any $k$ greater than $2$?

Answer 1

You're looking for this formula:

Let $A$ be a finite alphabet of size $q$. Let $n$ be a positive integer. Then, the number of Lyndon words of length $n$ over $A$ is \begin{align} \dfrac{1}{n} \sum\limits_{d \mid n} \mu\left(d\right) q^{n/d} , \end{align} where $\mu$ stands for the number-theoretical Möbius function (and where the sign $\sum\limits_{d \mid n}$ means a sum over all positive divisors of $n$).

I know of essentially two ways to prove this fact:

1. One proof uses the Chen-Fox-Lyndon factorization theorem, which says that any word can be uniquely factored as a product $w_1 w_2 \cdots w_k$ of Lyndon words $w_1, w_2, \ldots, w_k$ satisfying $w_1 \geq w_2 \geq \cdots \geq w_k$ (in lexicographic order). This theorem yields a generating-function relationship between the number of Lyndon words of a given size and the number of all words of a given size. The details of this proof can be found in the solution to Exercise 6.1.29 in Darij Grinberg and Victor Reiner, Hopf Algebras in Combinatorics, version of 19 April 2020 (also available as arXiv:1409.8356v6).

2. Another proof uses the fact that any aperiodic length-$n$ necklace (i.e., any size-$n$ orbit of length-$n$ words under cyclic rotation) contains exactly one Lyndon word, whereas any non-aperiodic length-$n$ necklace (i.e., any orbit of length-$n$ words under cyclic rotation that has smaller size than $n$) contains no Lyndon words. This fact shows that the number of Lyndon words of length $n$ equals the number of aperiodic length-$n$ necklaces. The latter number can be computed fairly easily using Möbius inversion and elementary group theory (specifically, the structure of cyclic groups and the orbit-stabilizer theorem). The details of this proof can be found in the solution to Exercise 6.1.34(h) in Darij Grinberg and Victor Reiner, Hopf Algebras in Combinatorics, version of 19 April 2020.

I am self-citing because of course I'm too lazy to look in the literature. You probably don't really want to read my solutions if you can help it. At the beginning of §6.1 of Hopf Algebras in Combinatorics, you can find some references to other sources on Lyndon words.

EDIT: Doesn't Theorem 3.3 in the paper you cited say exactly this?