Strings over $GF(2)$ 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(2)$ 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(2) = \mathbb{Z}_2$.
|
| (trace,subtrace) |
| $n$
| (0,0)
| (0,1)
| (1,0)
| (1,1)
|
| 1 |
1 | 0 | 1
| 0
|
|---|
| 2 |
1 | 1 | 2
| 0
|
|---|
| 3 |
1 | 3 | 3
| 1
|
|---|
| 4 |
2 | 6 | 4
| 4
|
|---|
| 5 |
6 | 10 | 6
| 10
|
|---|
| 6 |
16 | 16 | 12
| 20
|
|---|
| 7 |
36 | 28 | 28
| 36
|
|---|
| 8 |
72 | 56 | 64
| 64
|
|---|
| 9 |
136 | 120 | 136
| 120
|
|---|
| 10 |
256 | 256 | 272
| 240
|
|---|
| 11 |
496 | 528 | 528
| 496
|
|---|
| 12 |
992 | 1056 | 1024
| 1024
|
|---|
| 13 |
2016 | 2080 | 2016
| 2080
|
|---|
| 14 |
4096 | 4096 | 4032
| 4160
|
|---|
| 15 |
8256 | 8128 | 8128
| 8256
|
|---|
| 16 |
16512 | 16256 | 16384
| 16384
|
|---|
| 17 |
32896 | 32640 | 32896
| 32640
|
|---|
| 18 |
65536 | 65536 | 65792
| 65280
|
|---|
| 19 |
130816 | 131328 | 131328
| 130816
|
|---|
| 20 |
261632 | 262656 | 262144
| 262144
|
|---|
Examples
The two binary strings of trace 1, subtrace 0 and length 2 are $\{10, 01\}$.
The three binary strings of trace 0, subtrace 1 and length 3 are $\{ 011, 101, 110\}$.
The four binary strings of trace 1, subtrace 1 and length 4 are $\{0111, 1011, 1101, 1110\}$.
Enumeration (OEIS)
-
The number $S(n;t,s)$ can be computed from the following recurrence relation
\begin{align}
S(n;t,s) &= S(n-1;t,s) + S(n-1;t-1,s-(t-1)) \\
&= S(n-1;t,s) + S(n-1;t+1,s+t+1).
\end{align}
Note that all operations involving operands $t$ or $s$ are carried out over $GF(2)$.
-
Column (0,0) is OEIS A038503.
-
Column (0,1) is OEIS A038505.
-
Column (1,0) is OEIS A038504.
-
Column (1,1) is OEIS A000749.