# Binary words 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 $\{0,1,\ldots,k-1\}$ with $k=2$ that have trace $t$ and subtrace $s$. The trace of a $k$-ary word is the sum of its digits mod $k$, i.e., $t=a_1+a_2+\cdots+a_n \pmod{k}$. The subtrace is the sum of the products of all $n(n-1)/2$ pairs of digits taken mod $k$, i.e., $s=\sum_{1\leq i\lt j\leq n} a_i a_j$.

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 0, subtrace 0 and length 4 are $\{0000, 1111\}$. 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}
• Column (0,0) is OEIS A038503. The value is $\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots$ which has the closed form expression $(2^n+(1+i)^n+(1-i)^n)/4$, where $i=\sqrt{-1}$. The $i$ can be eliminated to get $(2^n+2 \sqrt{2}^n \cos(\pi n/4)/4$. The sequence has the rational generating function $(1-x)^3 /((1-x)^4 -x^4)$.
• Column (0,1) is OEIS A038505. The value is $\binom{n}{2}+\binom{n}{6}+\binom{n}{10}+\cdots$ which has the closed form expression $(2^n-(1+i)^n -(1-i)^n)/4$, where $i=\sqrt{-1}$. The $i$ can be eliminated to get $(2^n-2 \sqrt{2}^n \cos(\pi n/4)/4$. The sequence has the rational generating function $x^2 (1-x)/((1-x)^4 -x^4)$.
• Column (1,0) is OEIS A038504. The value is $\binom{n}{1}+\binom{n}{5}+\binom{n}{9}+\cdots$ which has the closed form expression $(2^n-i(1+i)^n+i(1-i)^n)/4$, wgere $i=\sqrt{-1}$. The $i$ can be eliminated to get $(2^n+2 \sqrt{2}^n \sin(\pi n/4)/4$. The sequence has the rational generating function $x(1-x)^2 /((1-x)^4 -x^4)$.
• Column (1,1) is OEIS A00749. The value is $\binom{n}{3}+\binom{n}{7}+\binom{n}{11}+\cdots$ which has the closed form expression $(2^n+i(1+i)^n-i(1-i)^n)/4$, where $i=\sqrt{-1}$. The $i$ can be eliminated to get $(2^n-2 \sqrt{2}^n \sin(\pi n/4)/4$. The sequence has the rational generating function $x^3 /((1-x)^4 -x^4)$.