The Combinatorial Object Server

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

	(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 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)$.