The number of qary Lyndon words
with given trace mod q.
A qary Lyndon word is a string made from the characters
0, 1, ..., q1, i.e. the integers mod q.
It must be aperiodic (not equal to any of its nontrivial rotations) and
be lexicographically least among its rotations.
Here we consider the set L(n;t) of length
n
lyndon words
a_{1}a_{2}···a_{n}
over the alphabet {0,1,.., q1}, i.e. Z_{q} , that have trace t.
The trace of a qary lyndon word
is the sum of its digits mod q, i.e.
t = a_{1}+a_{2}+ ··· +a_{n}
mod q.
 binary
 ternary
 4ary
 5ary
 6ary

 (trace) 
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 6ary 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 4ary Lyndon words of trace 2 and length
3 are { 002, 011, 033, 123, 132 }.
Further Notes:

The number of Lyndon words with trace 1 is equal to the number
of irreducible polynomials over GF(q) with nonzero trace.
See this the page
www.theory.cs.uvic.ca/inf/trs/poly/Fq/poly_tr_Fq.html
for more info.

Let L_{q}(n,t) denote the number
of qary lyndon words of trace t and length n.
L_{q}(n,t) =

1 

qn 



gcd(d,q)
µ(d) q ^{n/d} .


The number of qary Lyndon words with given trace is the same whenever
the gcd of the traces with q is the same.
Further, if q is the power of a prime p, then the number
is the same for trace 0, p, p^{2},...

The binary trace 0 entry is sequence
A051841 in
Neil J. Sloane's
database
of integer sequences.
The binary trace 1 entry is sequence
A000048 in
Neil J. Sloane's
database
of integer sequences.
The ternary trace = 0 entry is sequence
A046209 in
Neil J. Sloane's
database
of integer sequences.
The ternary trace = 1,2 entry is sequence
A046211 in
Neil J. Sloane's
database
of integer sequences.
The 4ary trace = 0,2 entry is sequence
A054664 in
Neil J. Sloane's
database
of integer sequences.
The 4ary trace = 1,3 entry is sequence
A054660 in
Neil J. Sloane's
database
of integer sequences.
The 5ary trace = 0 entry is sequence
A054663 in
Neil J. Sloane's
database
of integer sequences.
The 5ary trace = 1,2,3,4 entry is sequence
A054662 in
Neil J. Sloane's
database
of integer sequences.
The 6ary trace = 0 entry is sequence
A054665 in
Neil J. Sloane's
database
of integer sequences.
The 6ary trace = 1,5 entry is sequence
A054666 in
Neil J. Sloane's
database
of integer sequences.
The 6ary trace = 2,4 entry is sequence
A054667 in
Neil J. Sloane's
database
of integer sequences.
The 6ary trace = 3 entry is sequence
A054700 in
Neil J. Sloane's
database
of integer sequences.
Questions?? Email
The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding
email address.)
Created December 13, 1999 by Frank Ruskey.
It was last updated Wednesday, 10May2006 10:32:14 PDT.
There have been 3219 visitors to this page since May 16, 2000
.
©Frank Ruskey, 19952003.