# 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$.

1 2 3 4 5 (trace,subtrace) $n$ (0,0) (0,1) (1,0) (1,1) 1 0 1 0 1 1 2 0 1 3 3 1 2 6 4 4 6 10 6 10 16 16 12 20 36 28 28 36 72 56 64 64 136 120 136 120 256 256 272 240 496 528 528 496 992 1056 1024 1024 2016 2080 2016 2080 4096 4096 4032 4160 8256 8128 8128 8256 16512 16256 16384 16384 32896 32640 32896 32640 65536 65536 65792 65280 130816 131328 131328 130816 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.