A q-ary Lyndon word is a string made from the characters 0, 1, ..., q-1, i.e. the integers mod q. It must be aperiodic (not equal to any of its non-trivial rotations) and be lexicographically least among its rotations.

Here we consider the set L(n;t) of length n lyndon words a₁a₂···a_n over the alphabet {0,1,.., q-1}, i.e. Z_q , that have trace t. The trace of a q-ary lyndon word is the sum of its digits mod q, i.e. t = a₁+a₂+ ··· +a_n mod q.

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 }.

Further Notes:

• The number of Lyndon words with trace 1 is equal to the number of irreducible polynomials over GF(q) with non-zero 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 q-ary lyndon words of trace t and length n.

  Lq(n,t)   =

  1 qn

  __ \ /    d | n

  gcd(d,q) µ(d) q n/d .

  gcd(d,q) | t

• The number of q-ary 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²,...

• 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 4-ary trace = 0,2 entry is sequence A054664 in Neil J. Sloane's database of integer sequences.
  The 4-ary trace = 1,3 entry is sequence A054660 in Neil J. Sloane's database of integer sequences.
  The 5-ary trace = 0 entry is sequence A054663 in Neil J. Sloane's database of integer sequences.
  The 5-ary trace = 1,2,3,4 entry is sequence A054662 in Neil J. Sloane's database of integer sequences.
  The 6-ary trace = 0 entry is sequence A054665 in Neil J. Sloane's database of integer sequences.
  The 6-ary trace = 1,5 entry is sequence A054666 in Neil J. Sloane's database of integer sequences.
  The 6-ary trace = 2,4 entry is sequence A054667 in Neil J. Sloane's database of integer sequences.
  The 6-ary 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, 10-May-2006 10:32:14 PDT.
There have been 2085 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.