Counting particular odd-length strings over a two letter alphabet.

Question

OEIS sequence A297789 describes

The number of [equivalence classes of] length $2n - 1$ strings over the alphabet $\{0, 1\}$ such that the first half of any initial odd-length substring is a permutation of the second half.

Two strings are in the same equivalence class if they are the same up to swapping the letters of the alphabet.

1, 2, 3, 4, 7, 11, 17, 25, 49, 75, 129, 191, 329, 489, 825, 1237, 2473, 3737, 6329, 9435, 16833, 25081, 41449, 61043, 115409, 172441, 290617

For example, $1010110101101$ is such a string because:

initial odd substring | first half | second half
----------------------+------------+------------
  1                   | 1          | 1
  101                 | 10         | 01
  10101               | 101        | 101
  1010110             | 1010       | 0110
  101011010           | 10101      | 11010
  10101101011         | 101011     | 101011
  1010110101101       | 1010110    | 0101101

---

Question

I have two conjectures based on the first few terms:

• $A297789(2^k + 1) = 2\cdot A297789(2^k) - 1$ for $k > 0$, and
• $A297789(n)$ is odd for all $n > 4$.

Is there a proof or counter-example to these conjectures?

---

It's worth noting that the strings that A297789 counts can be put on a binary tree. Perhaps this is a useful lens?

Answer 1

Here's a proof of the first conjecture.

Preliminary remarks

Let's call "balanced strings" those described by that sequence.

Let $s$ be a balanced binary string of length $2n-1$. We denote $s_i$ its $i$-th bit (indexed from $1$), and $s_i^j$ the substring of bits from $i$ to $j$ (inclusive). The number of $1$ is denoted $|s|$.

Note that another way to say that two binary strings are permutations of each other is that they have the same numbers of $0$ and $1$: $s$ being balanced is equivalent to saying that for every $i < n$, $|s_1^n| = |s_n^{2n-1}|$.

This implies that every odd prefix is also balanced. Conversely, we can generate balanced strings by appending two bits at a time. This is also suggested by the binary tree you drew above.

How many ways are there to extend $s$ into a balanced string of length $2(n+1)-1$? We enumerate pairs of bits, $s_{2n}$ and $s_{2n+1}$, such that $|s_1^{n+1}| = |s_{n+1}^{2n+1}|$. We must consider four cases of the possible values for the middle bits $s_n$ and $s_{n+1}$. Here's one:

• If $s_n = 0$ and $s_{n+1} = 1$, then

  $$\begin{aligned} |s_1^{n+1}| &= |s_1^n| + 1 \\ &= |s_n^{2n-1}| + 1 \quad \text{(since $s$ is balanced)}\\ &= |s_{n+1}^{2n-1}| + 1 \end{aligned}$$

  For that to be equal to $|s_{n+1}^{2n+1}|$, the new bits can be either $01$ or $10$ (two choices).

The conclusion is that if $s_n \neq s_{n+1}$, then there are two ways to extend $s$ (with $01$ or $10$), otherwise there is only one.

Main result

$A297789(2^k+1)=2⋅A297789(2^{k})−1$ for $k>0$

As a consequence of the previous intermediate result, that is equivalent to claiming that every balanced string of length $2^{k+1}-1$ can be extended in exactly two ways, except the one string made of all ones.

That, in turn, amounts to saying that in every balanced string $s$ of length $2^{k+1}-1$, the middle bits $s_{2^k}$ and $s_{2^k+1}$ are distinct. In that case, the new bits we append at the end are $01$ or $10$, i.e., also distinct. Interesting coincidence, we can thus prove that claim by induction on $k$.