Strings over $GF(3)$ with given trace and subtrace
Here we consider the number $S(n;t,s)$ of length $n$ words $a_1 a_2 \ldots a_n$ over the alphabet consisting of the elements of the field $GF(3)$ that have trace $t$ and subtrace $s$.
The
trace of a word is the sum of its digits over the field, i.e., $t = a_1 + a_2 + \cdots + a_n$.
The
subtrace is the sum of the products of all $n(n-1)/2$ pairs of digits taken over the field, i.e., $s = \sum_{1\leq i\lt j\leq n} a_i a_j$.
Note that $GF(3) = \mathbb{Z}_3$.
|
| (trace,subtrace) |
| $n$
| (0,0)
| (0,1)
| (0,2)
| (1,0)
(2,0)
| (1,1)
(2,1)
| (1,2)
(2,2)
|
| 1 |
1 | 0 | 0
| 1 | 0 | 0
|
|---|
| 2 |
1 | 0 | 2
| 2 | 1 | 0
|
|---|
| 3 |
3 | 0 | 6
| 3 | 3 | 3
|
|---|
| 4 |
9 | 6 | 12
| 9 | 6 | 12
|
|---|
| 5 |
21 | 30 | 30
| 30 | 21 | 30
|
|---|
| 6 |
63 | 90 | 90
| 81 | 81 | 81
|
|---|
| 7 |
225 | 252 | 252
| 225 | 252 | 252
|
|---|
| 8 |
729 | 756 | 702
| 702 | 729 | 756
|
|---|
| 9 |
2187 | 2268 | 2106
| 2187 | 2187 | 2187
|
|---|
| 10 |
6561 | 6642 | 6480
| 6561 | 6642 | 6480
|
|---|
| 11 |
19845 | 19602 | 19602
| 19602 | 19845 | 19602
|
|---|
| 12 |
59535 | 58806 | 58806
| 59049 | 59049 | 59049
|
|---|
| 13 |
177633 | 176904 | 176904
| 177633 | 176904 | 176904
|
|---|
| 14 |
531441 | 530712 | 532170
| 532170 | 531441 | 530712
|
|---|
| 15 |
1594323 | 1592136 | 1596510
| 1594323 | 1594323 | 1594323
|
|---|
| 16 |
4782969 | 4780782 | 4785156
| 4782969 | 4780782 | 4785156
|
|---|
| 17 |
14344533 | 14351094 | 14351094
| 14351094 | 14344533 | 14351094
|
|---|
| 18 |
43033599 | 43053282 | 43053282
| 43046721 | 43046721 | 43046721
|
|---|
| 19 |
129127041 | 129146724 | 129146724
| 129127041 | 129146724 | 129146724
|
|---|
| 20 |
387420489 | 387440172 | 387400806
| 387400806 | 387420489 | 387440172
|
|---|
Examples
The one ternary string of trace 2, subtrace 1 and length 2 is $\{11\}$.
The three ternary strings of trace 0, subtrace 0 and length 3 are $\{ 000, 111, 222\}$.
The three ternay strings of trace 1, subtrace 2 and length 3 are $\{112, 121, 211\}$.
Enumeration (OEIS)
-
The number $S(n;t,s)$ can be computed from the following recurrence relation
\[
S(n;t,s) = S(n-1;t,s) + S(n-1;t-1,s-(t-1)) + S(n-1;t-2,s-2(t-2)).
\]
Note that all operations involving operands $t$ or $s$ are carried out over $GF(3)$.
-
Column (0,0) is OEIS A073947.
-
Column (0,1) is OEIS A073948.
-
Column (0,2) is OEIS A073949.
-
Column (1,0),(2,0) is OEIS A073950.
-
Column (1,1),(2,1) is OEIS A073951.
-
Column (1,2),(2,2) is OEIS A073952.