3
$\begingroup$

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?

A297789 Tree

$\endgroup$
  • $\begingroup$ Why no strings starting with 0? $\endgroup$ – Fabio Somenzi Jan 28 '18 at 3:31
  • $\begingroup$ Technically the sequence counts equivalence classes, where two strings are in the same equivalence class if they’re the same under swapping letters of the alphabet. $\endgroup$ – Peter Kagey Jan 28 '18 at 3:53
  • 1
    $\begingroup$ Shouldn't the definition either mention the equivalence classes or, more simply, say something like "strings starting with 1?" $\endgroup$ – Fabio Somenzi Jan 28 '18 at 4:02
  • $\begingroup$ @FabioSomenzi I agree with you. $\endgroup$ – Li-yao Xia Jan 28 '18 at 5:34
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.