[Information Index] [Generation Index] [COS homepage]

The number of q-ary Lyndon words
with given trace mod q.

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 a1a2···an over the alphabet {0,1,.., q-1}, i.e. Zq , that have trace t. The trace of a q-ary lyndon word is the sum of its digits mod q, i.e. t = a1+a2+ ··· +an mod q.

binary ternary 4-ary 5-ary 6-ary
(trace)
n 0 1 01,2 0,21,3 01,2,3,4 01,5 2,43
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:

Further Notes:


[Information Index] [Generation Index] [COS homepage]

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 3216 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.