4-ary Lyndon words of given trace and subtrace.

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

	(trace,subtrace)
n	(0,0)	(0,1)	(0,2)	(0,3)	(1,0) (3,0)	(1,1) (3,1)	(1,2) (3,2)	(1,3) (3,3)	(2,0)	(2,1)	(2,2)	(2,3)
1	1	0	0	0	1	0	0	0	1	0	0	0
2	0	0	0	1	1	0	1	0	1	0	0	0
3	1	2	0	2	2	0	2	1	1	2	0	2
4	1	6	1	6	4	4	4	4	4	4	0	6
5	11	16	8	16	8	16	11	16	11	16	8	16
6	44	45	36	40	32	53	32	53	45	36	40	44
7	169	128	160	128	128	169	128	160	169	128	160	128
8	588	448	548	448	512	512	512	512	576	440	576	440
9	1948	1706	1920	1706	1948	1706	1920	1706	1948	1706	1920	1706
10	6560	6528	6496	6579	6963	6144	6963	6144	6579	6560	6528	6496
11	23133	24576	23040	24576	24576	23040	24576	23133	23133	24576	23040	24576
12	84565	90110	84565	90110	87380	87380	87380	87380	84820	90046	84480	90004
13	317755	327680	317440	327680	317440	327680	317755	327680	317755	327680	317440	327680
14	1198336	1198665	1197824	1198080	1179648	1217097	1179648	1217097	1198665	1197824	1198080	1198336

Examples:

The two 4-ary Lyndon words of trace 1, subtrace 2 and length 3 are ( 023, 032 }.
The four 4-ary Lyndon words of trace 3, subtrace 3 and length 4 are { 0111, 0133, 0313, 0331 }.
The six 4-ary Lyndon words of trace 2, subtrace 3 and length 4 are { 0123, 0132, 0213, 0231, 0312, 0321 }.

Further Notes:

If n is odd OR t is odd OR t = 0 (mod 4) and s odd OR t = 2 (mod 4) and s even, then the numbers above are
L(n;t,s) = 1/n sum_{k=0,1,2,3} sum_{d|n,d=2k+1(8)} mobius(d) S(n/d,(-1)^kt,(-1)^ks-kt²),
where S(n;t,s) is the number of 4-ary words with trace t and subtrace s. Tables of the S(n;t,s) numbers may be found on the page http://theory.cs.uvic.ca/inf/trs/str/Zq/str_tr_subtr_Z4.html
In the case where t is odd, this formula may be simplified to
L( n ; t, s ) = 1/n sum_{ d | n, d=1,3(4) } mobius(d) S( n/d, dt, ds-(d-1)/2 ).
There is a corresponding page for ternary Lyndon words.
Column (0,0) is sequence A068596 in Neil J. Sloane's database of integer sequences.
Column (0,1) is sequence A074403 in Neil J. Sloane's database of integer sequences.
Column (0,2) is sequence A074404 in Neil J. Sloane's database of integer sequences.
Column (0,3) is sequence A074405 in Neil J. Sloane's database of integer sequences.
Column (1,0),(3,0) is sequence A074406 in Neil J. Sloane's database of integer sequences.
Column (1,1),(3,1) is sequence A074407 in Neil J. Sloane's database of integer sequences.
Column (1,2),(3,2) is sequence A074408 in Neil J. Sloane's database of integer sequences.
Column (1,3),(3,3) is sequence A074409 in Neil J. Sloane's database of integer sequences.
Column (2,0) is sequence A074410 in Neil J. Sloane's database of integer sequences.
Column (2,1) is sequence A074411 in Neil J. Sloane's database of integer sequences.
Column (2,2) is sequence A074412 in Neil J. Sloane's database of integer sequences.
Column (2,3) is sequence A074413 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 1679 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.