login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; graph; refs; listen; history; text; internal format)
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, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 17:33 EST 2019. Contains 329287 sequences. (Running on oeis4.)