Section 7.2.1.1: Generating All n-Tuples

Exercise 102. [HM28] [HM28] Deduce the number of m-ary primes of length n from the unique factor- ization theorem in the previous exercise.

Verified: yes
Solve time: 1m18s

---

Setup

Let the alphabet have size $m$, totally ordered. A word of length $n$ is an $m$-ary string, so the total number of words of length $n$ is $m^n$.

Let $L_n$ denote the number of $m$-ary primes of length $n$, where “prime” means the objects used in the unique factorization theorem of Exercise 101, namely the Lyndon words in lexicographic order.

Let $W_n = m^n$.

The theorem from Exercise 101 states that every word $\alpha$ can be written uniquely in the form

$$ \alpha = \lambda_1 \lambda_2 \cdots \lambda_t, $$

where each $\lambda_j$ is prime and

$$ \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_t $$

in lexicographic order.

The goal is to determine $L_n$.

Solution

Each word is uniquely a nonincreasing sequence of primes, so the set of all words is the combinatorial class of multisets of primes, where each prime $\lambda$ contributes an atomic object of size $|\lambda|$.

For each fixed prime $\lambda$ of length $k$, any word may contain it $r \ge 0$ times, contributing total length $rk$. This produces the ordinary generating factor

$$ 1 + x^k + x^{2k} + \cdots = \frac{1}{1 - x^k}. $$

Since distinct primes are independent choices in the multiset representation, the generating function for all words is

$$ \sum_{n \ge 0} W_n x^n = \prod_{\lambda \ \text{prime}} \frac{1}{1 - x^{|\lambda|}}. $$

Grouping primes by length, there are $L_k$ primes of length $k$, so this becomes

$$ \sum_{n \ge 0} m^n x^n = \prod_{k \ge 1} (1 - x^k)^{-L_k}. $$

Taking logarithms of both sides yields

$$ \sum_{n \ge 1} \frac{m^n}{n} x^n

• \sum_{k \ge 1} L_k \log(1 - x^k). $$

Expanding the logarithm,

$$ -\log(1 - x^k) = \sum_{r \ge 1} \frac{x^{kr}}{r}, $$

so

$$ \sum_{n \ge 1} \frac{m^n}{n} x^n

\sum_{k \ge 1} L_k \sum_{r \ge 1} \frac{x^{kr}}{r}. $$

Reindex the right-hand side by $n = kr$. The coefficient of $x^n$ is

$$ \sum_{k \mid n} \frac{L_k}{n/k} = \frac{1}{n} \sum_{k \mid n} k L_k. $$

Equating coefficients of $x^n$ gives

$$ \frac{m^n}{n} = \frac{1}{n} \sum_{k \mid n} k L_k, $$

hence

$$ m^n = \sum_{k \mid n} k L_k. $$

This is a Dirichlet convolution identity between the functions $m^n$ and $k L_k$. Applying Möbius inversion,

$$ n L_n = \sum_{d \mid n} \mu(d), m^{n/d}. $$

Dividing by $n$ gives the required count:

$$ L_n = \frac{1}{n} \sum_{d \mid n} \mu(d), m^{n/d}. $$

Therefore the number of $m$-ary primes of length $n$ is

$$ \boxed{\frac{1}{n} \sum_{d \mid n} \mu(d), m^{n/d}}. $$

Verification

The identity $m^n = \sum_{k \mid n} k L_k$ has consistent base case $n=1$, since $m = 1 \cdot L_1$ implies $L_1 = m$, matching the fact that all single letters are primes.

The Möbius inversion step is valid because the summation depends only on divisors of $n$, forming a standard arithmetic convolution over the divisor lattice. Substituting the derived formula for $L_n$ back into $\sum_{k \mid n} k L_k$ reconstructs $m^n$ via cancellation $\sum_{d \mid n} \mu(d) = 0$ for $n > 1$ and $=1$ for $n=1$, ensuring exact recovery of the original sequence.

This completes the derivation. ∎