A341277 Number of length-n binary mesosome-avoiding strings.

1, 2, 4, 8, 14, 24, 32, 42, 54, 68, 82, 98, 118, 140, 162, 186, 216, 248, 280, 314, 356, 400, 444, 490, 546, 604, 662, 722, 794, 868, 942, 1018, 1108, 1200, 1292, 1386, 1496, 1608, 1720, 1834, 1966, 2100, 2234, 2370, 2526, 2684, 2842, 3002, 3184, 3368, 3552

Offset

0,2

Comments

A mesosome is a word of the form x x', where x' is a cyclic shift of x, different from x. A string is mesosome-avoiding if it has no subword (contiguous block) that is a mesosome.

Links

Table of n, a(n) for n=0..50.

Robert Cummings, Jeffrey Shallit and Paul Staadecker, Mesosome Avoidance, arXiv:2107.13813 [cs.DM], 2021.

Formula

Let n = 4k + i for i = 0, 1, 2, 3 and n >= 5. Then:

a(4k ) = (4k^3 + 15k^2 + 41k - 12)/3;

a(4k + 1) = (4k^3 + 18k^2 + 50k )/3;

a(4k + 2) = (4k^3 + 21k^2 + 59k + 12)/3;

a(4k + 3) = (4k^3 + 24k^2 + 68k + 30)/3. [from 'Mesosome Avoidance', Theorem 2, eqn. (1), Georg Fischer, Nov 25 2022]

Example

For n = 4 the only strings not counted are 0110 and 1001.

Crossrefs

Sequence in context: A018153 A101687 A096461 * A049701 A005598 A290845

Adjacent sequences: A341274 A341275 A341276 * A341278 A341279 A341280

Keyword

nonn

Author

Jeffrey Shallit, Feb 08 2021

Status

approved