5-ary Lyndon words with given trace and subtrace.

A 5-ary Lyndon word is a string made from the characters 0, 1, 2, 3, 4. 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,s) of length n lyndon words a₁a₂···a_n over the alphabet {0,1,2,3,4} that have trace t and subtrace s. The trace of a 5-ary lyndon word is the sum of its digits mod 5, i.e. t = a₁+a₂+ ··· +a_n mod 5. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken mod 5, i.e. s = SUM( a_ia_j : 1 < i < j < n ).

	(trace,subtrace)
n	(0,0)	(0,1) (0,4)	(0,2) (0,3)	(1,0) (2,0) (3,0) (4,0)	(1,1) (2,4) (3,4) (4,1)	(1,2) (2,3) (3,3) (4,2)	(1,3) (2,2) (3,2) (4,3)	(1,4) (2,1) (3,1) (4,4)
1	1	0	0	1	0	0	0	0
2	0	1	0	1	0	0	1	0
3	0	2	2	2	2	0	2	2
4	6	5	7	5	6	5	7	7
5	24	20	30	25	25	25	25	25
6	104	99	107	104	99	107	107	99
7	432	450	450	450	450	450	450	432
8	1950	1965	1935	1935	1965	1950	1965	1935
9	8736	8666	8666	8666	8736	8666	8666	8666
10	39298	38985	38990	39050	39050	39050	39050	39050
11	177784	177500	177500	177784	177500	177500	177500	177500
12	813748	814006	813490	814006	813490	813490	814006	813748
13	3755048	3756250	3756250	3756250	3756250	3755048	3756250	3756250
14	17438400	17437275	17439507	17437275	17438400	17437275	17439507	17439507
15	81380192	81374990	81385410	81380200	81380200	81380200	81380200	81380200

Examples:

The two 5-ary Lyndon words of trace 2, subtrace 4 and length 3 are ( 124, 142 }.
The five 5-ary Lyndon words of trace 1, subtrace 2 and length 4 are { 0222, 1113, 1244, 1424, 1442 }.
The seven 5-ary Lyndon words of trace 3, subtrace 1 and length 4 are { 0044, 0233, 0323, 0332, 1124, 1142, 1214 }.

Further Notes:

Column (0,0) is sequence A074414 in Neil J. Sloane's database of integer sequences.
Column (0,1),(0,4) is sequence A074415 in Neil J. Sloane's database of integer sequences.
Column (0,2),(0,3) is sequence A074416 in Neil J. Sloane's database of integer sequences.
Column (1,0),(2,0),(3,0),(4,0) is sequence A074417 in Neil J. Sloane's database of integer sequences.
Column (1,1),(2,4),(3,4),(4,1) is sequence A074418 in Neil J. Sloane's database of integer sequences.
Column (1,2),(2,3),(3,3),(4,2) is sequence A074419 in Neil J. Sloane's database of integer sequences.
Column (1,3),(2,2),(3,2),(4,3) is sequence A074420 in Neil J. Sloane's database of integer sequences.
Column (1,4),(2,1),(3,1),(4,4) is sequence A074421 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.)
It was last updated Wednesday, 10-May-2006 10:32:13 PDT.
There have been 1664 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.