Lyndon words over F₂ of given trace and subtrace.

Here we consider the set L(n;t,s) of length n lyndon words a₁a₂···a_n over the alphabet consisting of the elements of the field F₂ that have trace t and subtrace s. The trace of a lyndon word is the sum of its digits over the field F₂ , i.e. t = a₁+a₂+ ··· +a_n. The subtrace is the sum of the products of all n(n-1)/2 pairs of digits taken over the field F₂ , i.e. s = SUM( a_ia_j : 1 < i < j < n ). Note that F₂ = Z₂ .

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

Lyndon words over F2 of given trace and subtrace.

Examples:

Further Notes:

Lyndon words over F₂ of given trace and subtrace.