![[Information Index]](ico/objinfo.gif)
![[Generation Index]](ico/objgen.gif)
![[COS homepage]](ico/cos.gif)
The number of Lyndon words over Fq
with given trace.
Here we consider the set L(n;t) of length
n lyndon
words a1a2···an
over the alphabet consisting of the elements of
the field Fq that
have trace t.
The trace of a lyndon word
is the sum of its digits over the field Fq , i.e.
t = a1+a2+ ··· +an.
Below we use x = RootOf( z2+z+1 )
and y = 1+x.
|
| binary
| ternary
| 4-ary
| 5-ary
|
|
| (trace) |
| n
| 0 | 1
| 0 | 1,2
| 0 | 1,x,y
| 0 | 1,2,3,4
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 2 |
0 |
1 |
1 |
1 |
0 |
2 |
2 |
2 |
| 3 |
1 |
1 |
2 |
3 |
5 |
5 |
8 |
8 |
| 4 |
1 |
2 |
6 |
6 |
12 |
16 |
30 |
30 |
| 5 |
3 |
3 |
16 |
16 |
51 |
51 |
124 |
125 |
| 6 |
4 |
5 |
38 |
39 |
160 |
170 |
516 |
516 |
| 7 |
9 |
9 |
104 |
104 |
585 |
585 |
2232 |
2232 |
| 8 |
14 |
16 |
270 |
270 |
2016 |
2048 |
9750 |
9750 |
| 9 |
28 |
28 |
726 |
729 |
7280 |
7280 |
43400 |
43400 |
| 10 |
48 |
51 |
1960 |
1960 |
26112 |
26214 |
195248 |
195250 |
| 11 |
93 |
93 |
5368 |
5368 |
95325 |
95325 |
887784 |
887784 |
| 12 |
165 |
170 |
14736 |
14742 |
349180 |
349520 |
4068740 |
4068740 |
| 13 |
315 |
315 |
40880 |
40880 |
1290555 |
1290555 |
18780048 |
18780048 |
| 14 |
576 |
585 |
113828 |
113828 |
4792320 |
4793490 |
87191964 |
87191964 |
| 15 |
1091 |
1091 |
318848 |
318864 |
17895679 |
17895679 |
| 16 |
2032 |
2048 |
896670 |
896670 |
Examples:
-
The two ternary Lyndon words of trace 0 and length
3 are { 021, 012 }.
-
The five 4-ary Lyndon words of trace y and length
3 are { 00y, 01x, 0x1, 11y,
xxy }.
-
The two binary Lyndon words of trace 1 and length
4 are { 0001, 0111 }.
Further Notes:
-
The binary trace 0 entry is sequence
A051841 in
Neil J. Sloane's
database
of integer sequences.
The binary trace 1 entry is sequence
A000048 in
Neil J. Sloane's
database
of integer sequences.
The ternary trace = 0 entry is sequence
A046209 in
Neil J. Sloane's
database
of integer sequences.
The ternary trace = 1,2 entry is sequence
A046211 in
Neil J. Sloane's
database
of integer sequences.
The 4-ary trace = 0 entry is sequence
A054661 in
Neil J. Sloane's
database
of integer sequences.
The 4-ary trace = 1,x,y entry is sequence
A054660 in
Neil J. Sloane's
database
of integer sequences.
The 5-ary trace = 0 entry is sequence
A054663 in
Neil J. Sloane's
database
of integer sequences.
The 5-ary trace = 1,2,3,4 entry is sequence
A054662 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.)
Created December 13, 1999 by Frank Ruskey.
It was last updated Wednesday, 10-May-2006 10:32:13 PDT.
There have been 1967 visitors to this page since May 16, 2000
.
©Frank Ruskey, 1995-2003.