Binary Lyndon words with given trace and subtrace.

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

	(trace,subtrace)
n	(0,0)	(0,1)	(1,0)	(1,1)
1	1	0	1	0
2	0	0	1	0
3	0	1	1	0
4	0	1	1	1
5	1	2	1	2
6	2	2	2	3
7	5	4	4	5
8	8	6	8	8
9	15	13	15	13
10	24	24	27	24
11	45	48	48	45
12	80	85	85	85
13	155	160	155	160
14	288	288	288	297
15	550	541	541	550
16	1024	1008	1024	1024
17	1935	1920	1935	1920
18	3626	3626	3654	3626
19	6885	6912	6912	6885
20	13056	13107	13107	13107

Examples:

The one binary Lyndon word of trace 1, subtrace 0 and length 3 is ( 001 }.
The two binary Lyndon words of trace 0, subtrace 1 and length 5 are { 00011, 00101 }.
The two binary Lyndon words of trace 0, subtrace 0 and length 6 are { 001111, 010111 }.

Further Notes:

Column (0,0) is sequence A074027 in Neil J. Sloane's database of integer sequences.
Column (0,1) is sequence A074028 in Neil J. Sloane's database of integer sequences.
Column (1,0) is sequence A074029 in Neil J. Sloane's database of integer sequences.
Column (1,1) is sequence A074030 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 805 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.