Number of different counts of $1$s in sliding windows

Consider a tuple $A = (a_1, \dots, a_{2n-1})$ where $a_i \in \{0,1\}$. For each sub-tuple of length $n$ in order from left to right, that is $(a_i, \dots, a_{i+n-1})$ for all $i$, we count the number of $1$s and output the result as a "counting tuple". For example if $n = 3$ and $A= (1,0,1,1,1)$ the resulting counting tuple is $C_A = (2,2,3)$.

Not every different tuple $A$ gives a different counting tuple. For example for $n = 3$, if $A= (1,0,1,1,0)$ we get the counting tuple $C_A = (2,2,2)$ which is the same as we get for $A' = (0,1,1,0,1)$.

For a given $n$, what is the total number of distinct counting tuples $C_A$ taken over all $2^{2n-1}$ possible input tuples $A$?

@orlp has found that $3^{n-2}(n+5)$ fits perfectly for $n \leq 13$. Is it possible to prove this is the right formula? The sequence also occurs at https://oeis.org/A038765 .

Write the tuple $A$ in two rows. For example, for $n=8$, you might have $$\begin{array}{rccccccc}(0&1&1&0&0&1&0&0)\\1&0&1&0&0&1&1\end{array}$$ The counting tuple in this example must start with $3$, the number of ones in the first row. When the window shifts one place to the right, the first bit in the first row drops out, while the first bit in the second row enters: $$\begin{array}{lrcccccc}\bf0&(1&1&0&0&1&0&0\\\bf1)&0&1&0&0&1&1\end{array}$$ The next number in the counting tuple must be one less, one more, or the same as the previous number, depending on the contents of the column: $$\begin{array}{crrc}{0\atop0}&{0\atop1}&{1\atop0}&{1\atop1 }\\\hline\text{same}&+1&-1&\text{same}\end{array}$$ So the counting tuple is a walk with steps of $-1,0,$ and $+1$. In this example, the walk is $(3,4,3,3,3,3,3,4)$. However, the walk has conditions: the number of $+1$ steps cannot be more than the number of zeros in the first row (ignoring the final bit), and the number of $-1$ steps cannot be more than the number of ones in the first row (ignoring the final bit).

That means that if the counting tuple starts with $k$, then:

• If the last bit in the first row is $0$, then the walk contains no more than $k$ steps down and $n-1-k$ steps up.
• If the last bit in the first row is $1$, then the walk contains no more than $k-1$ steps down and $n-k$ steps up.

Thus, a viable counting tuple starts with a number $k$ and is followed by a walk of length $n-1$ with no more than $k$ steps down and no more than $n-k$ steps up. Rather than try to count these directly by $k$, instead imagine that you have covered up the first row of some tuple $A$, and must write down a second. At each step, there are two choices: ask for the opposite bit to what appears in the first row, or the same bit. If you always ask for the opposite bit, then $k$ can only take one of two possible values. If you ask for a matching bit on $m$ occasions, then $k$ can take one of $m+2$ possible values. Therefore, the number of possible counting tuples with $m$ horizontal steps is $$(m+2)\cdot\binom{n-1}{m}\cdot 2^{n-1-m}$$ Summing over $m$, you get something of the form $$f(n)=2\cdot\tbinom{n-1}0\cdot 2^{n-1}+3\cdot\tbinom{n-1}1\cdot 2^{n-2}+4\cdot\tbinom{n-1}2\cdot 2^{n-3}+\cdots$$

To simplify this answer, consider the following expression, with its binomial expansion: $$x^2(2+x)^{n-1}=2^{n-1}x^2+\tbinom{n-1}12^{n-2}x^3+\cdots$$

Differentiating both sides with respect to $x$, you get $$2x(2+x)^{n-1}+x^2(n-1)(2+x)^{n-2}=2x\cdot 2^{n-1}+3x^2\cdot\tbinom{n-1}1\cdot 2^{n-2}+\cdots$$

Setting $x=1$, $$2\cdot 3^{n-1}+(n-1)\cdot 3^{n-2}=f(n)$$

Simplifying, the final result is $$f(n)=(n+5)\cdot 3^{n-2}$$

• Nice to see my conjecture confirmed. – orlp Jun 1 '17 at 13:36

Conjecture, $f(n) = 3^{n-2}(n+5)$.

The first actual values of $f(1), f(2), \dots$ are, which are all correct:

$$[2, 7, 24, 81, 270, 891, 2916, 9477, 30618, 98415, 314928, 1003833, 3188646]$$

Looking that up in OEIS gives the above formula, and relates it to the number of different ways we can have a $n$-catafusene, with a single tetragon in the chain somewhere.

I can't prove the relation or the formula at the moment, but it seems quite plausible.

• Fascinating. Thank you. – user66307 May 31 '17 at 13:30

Disclaimer: Sorry that try is not correct.

My guess is $t_n=2^{n-1}$ once $n>2$:

• $t_3=4=2^2$ is just the possible numbers of $1$s in a three-set.

• If $t_n$ is known, then for any tuple $A$ of length $n$ giving a count $C_A$, we can build two tuples $B=A\cup \{1\}$ and $B'=A\cup \{0\}$ of length $n+1$ that will give different counts $C_{B}$ and $C_{B'}$. Obviously, all the counts you build in that way with one represent of each count of length $n$ will be different counts of length $n+1$ (either the n-2 first number differ, or the last one differs). Hence $t_{n+1}>=2*t_n$.

edit: the bold part is wrong. I'll try to fix that soon...

• Reciproquely, if $C_B$ is a count of length $n+1$, then removing the last element of $B$ will give you a tuple of length $n$ $A$, so $t_{n+1}<=2*t_n$

• Finally, $t_{n+1}=2*t_n$ and $t_n=2^{n-1}$ once $n>2$