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 ).

Below we use x = RootOf( z²+z+1 ) and y = 1+x.

	(trace,subtrace)
n	(0,0)	(0,1) (0,x) (0,y)	(1,0) (x,0) (y,0)	(1,1) (x,y) (y,x)	(1,x) (1,y) (x,1) (x,x) (y,1) (y,y)
1	1	0	1	0	0
2	0	0	1	1	0
3	2	1	1	2	1
4	6	2	4	4	4
5	15	12	15	12	12
6	40	40	45	45	40
7	153	144	144	153	144
8	528	496	512	512	512
9	1841	1813	1841	1813	1813
10	6528	6528	6579	6579	6528
11	23901	23808	23808	23901	23808
12	87550	87210	87380	87380	87380
13	322875	322560	322875	322560	322560
14	1198080	1198080	1198665	1198665	1198080
15	4474738	4473647	4473647	4474738	4473647

Examples:

The one 4-ary Lyndon word of trace y, subtrace x and length 2 is ( 1x }.
The two 4-ary Lyndon words of trace 0, subtrace 0 and length 3 are { 123, 132 }.
The two 4-ary Lyndon words of trace 0, subtrace 1 and length 4 are { 0011, 11xx }.

Further Notes:

Column (0,0) is sequence A074446 in Neil J. Sloane's database of integer sequences.
Column (0,1),(0,x),(0,y) is sequence A074447 in Neil J. Sloane's database of integer sequences.
Column (1,0),(x,0),(y,0) is sequence A074448 in Neil J. Sloane's database of integer sequences.
Column (1,1),(x,y),(y,x) is sequence A074449 in Neil J. Sloane's database of integer sequences.
Column (1,x),(1,y),(x,1),(x,x),(y,1),(y,y) is sequence A074450 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 1168 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.

Lyndon words over F4 of given trace and subtrace.

Examples:

Further Notes:

Lyndon words over F₄ of given trace and subtrace.