A297789 The number 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.

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, 431385, 775641, 1157417, 1938713, 2908069, 5816137, 8786121, 14682489, 21774137, 39391673, 58815073, 97815385

Offset

1,2

Comments

a(n) counts equivalence classes up to swapping the letters of the alphabet.

a(n+1) <= 2*a(n).

Conjecture: lim_{n->infinity} a(n+1)/a(n) exists and is a value in [1, 2]. [The following comment suggests that on the contrary, this limit may not exist. - N. J. A. Sloane, Jan 30 2018, following a comment from Peter Kagey, Jan 29 2017]

From Peter Kagey, Jan 27 2018: (Start)

a(2^k + 1) = 2 * a(2^k) - 1 for n > 0.

Conjecture: a(n) is odd for all n > 4.

(End)

Links

Lars Blomberg, Table of n, a(n) for n = 1..61

Li-yao Xia, Mathematics Stack Exchange, Counting particular odd-length strings over a two letter alphabet.

Example

For n = 7, one of the a(7) = 17 strings of length 2*7-1 = 13 is "1010110101101" because the first half of every initial odd-length substring is a permutation of the second half.
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
For n = 5, the a(5) = 7 strings are:
  101101101,
  101101110,
  101010110,
  101010101,
  101011010,
  101011001, and
  111111111.

Crossrefs

Sequence in context: A221998 A165407 A039897 * A222122 A222024 A222025

Adjacent sequences: A297786 A297787 A297788 * A297790 A297791 A297792

Keyword

nonn

Author

Peter Kagey, Jan 22 2018

Extensions

a(28)-a(39) from Lars Blomberg, Feb 02 2018

Status

approved