A321162 Maximum number of unbordered conjugates for a binary word of length n.

1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 10, 10, 11, 12, 12, 12, 13, 13, 14, 14, 15, 16, 16, 16, 17, 17, 18, 18, 19

Offset

1,2

Comments

Two words are conjugate if one is a cyclic shift of the other, such as "enlist" and "listen". A word w is bordered if it has a nonempty prefix that is also a suffix (and not equal to w), such as the word "entanglement". Harju and Nowotka show that for length-n binary words, at most n/2 unbordered conjugates are possible.

Links

Table of n, a(n) for n=1..39.

T. Harju and D. Nowotka, Border correlation of binary words, J. Combin. Theory Ser. A 108 (2004), 331-341.

Example

For n = 10, the word 0000101101 has 10 distinct conjugates, but only 4 of them are unbordered: {0000101101, 1011010000, 1101000010, 0100001011}.  This is maximum for n = 10.

Crossrefs

Sequence in context: A330996 A056970 A212218 * A008668 A225643 A116563

Adjacent sequences: A321159 A321160 A321161 * A321163 A321164 A321165

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 10 2019

Extensions

a(25)-a(39) from Lars Blomberg, Jan 25 2019

Status

approved