The Combinatorial Object Server

$k$-ary Lyndon words with given trace mod $k$

A $k$-ary Lyndon word is a string made from the characters $\{0,1,\ldots,k-1\}$, i.e., the integers mod $k$. It must be aperiodic (not equal to any of its non-trivial rotations) and be lexicographically least among its rotations. Here we consider the number $L_k(n;t)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet $\{0,1,\ldots,k-1\}$, i.e., $\mathbb{Z}_k$, that have trace $t$. The trace of a $k$-ary Lyndon word is the sum of its digits mod $k$, i.e., $t = a_1 + a_2 + \cdots + a_n \pmod{k}$.

	(trace)
	binary		ternary		4-ary		5-ary		6-ary
$n$	0	1	0	1,2	0,2	1,3	0	1,2,3,4	0	1,5	2,4	3
1	1	1	1	1	1	1	1	1	1	1	1	1
2	0	1	1	1	1	2	2	2	2	3	2	3
3	1	1	2	3	5	5	8	8	11	12	12	11
4	1	2	6	6	14	16	30	30	51	54	51	54
5	3	3	16	16	51	51	124	125	259	259	259	259
6	4	5	38	39	165	170	516	516	1282	1296	1284	1293
7	9	9	104	104	585	585	2232	2232	6665	6665	6665	6665
8	14	16	270	270	2032	2048	9750	9750	34938	34992	34938	34992
9	28	28	726	729	7280	7280	43400	43400	186612	186624	186624	186612
10	48	51	1960	1960	26163	26214	195248	195250	1007510	1007769	1007510	1007769
11	93	93	5368	5368	95325	95325	887784	887784	5496925	5496925	5496925	5496925
12	165	170	14736	14742	349350	349520	4068740	4068740	30231741	30233088	30231792	30233034
13	315	315	40880	40880	1290555	1290555	18780048	18780048	167444795	167444795	167444795	167444795
14	576	585	113828	113828	4792905	4793490	87191964	87191964	932900050	932906715	932900050	932906715
15	1091	1091	318848	318864	17895679	17895679	406900992	406901000	5224277345	5224277604	5224277604	5224277345
16	2032	2048	896670	896670	67106816	67108864	1907343750	1907343750	29386526544	29386561536	29386526544	29386561536

Examples

The three 6-ary Lyndon words of trace 3 and length 2 are $\{03, 12, 45\}$. The two ternary Lyndon words of trace 0 and length 3 are $\{021, 012\}$. The five 4-ary Lyndon words of trace 2 and length 3 are $\{002, 011, 033, 123, 132\}$.

Enumeration (OEIS)

• The number of Lyndon words with trace 1 is equal to the number of irreducible polynomials over $GF(k)$ with non-zero trace.
• The number $L_k(n;t)$ of $k$-ary Lyndon words of trace $t$ and length $n$ is \[ L_k(n;t) = \frac{1}{kn} \sum_{\substack{d\vert n \\ \gcd(d,k)\vert t}} \gcd(d,k) \mu(d) k^{n/d}. \]
• The number of $k$-ary Lyndon words with given trace is the same whenever the $\gcd$ of the traces with $k$ is the same. Further, if $k$ is the power of a prime $p$, then the number is the same for trace $0, p, p^2 ,\ldots$.
• The binary trace 0 column is OEIS A051841.
• The binary trace 1 column is OEIS A000048.
• The ternary trace=0 column is OEIS A046209.
• The ternary trace=1,2 column is OEIS A046211.
• The 4-ary trace=0,2 column is OEIS A054664.
• The 4-ary trace=1,3 column is OEIS A054660.
• The 5-ary trace=0 column is OEIS A054663.
• The 5-ary trace=1,2,3,4 column is OEIS A054662.
• The 6-ary trace=0 column is OEIS A054665.
• The 6-ary trace=1,5 column is OEIS A054666.
• The 6-ary trace=2,4 column is OEIS A054667.
• The 6-ary trace=3 column is OEIS A054700.