A323595 Number of distinct sets of lengths of nonempty palindrome prefixes, over all binary words of length n.

1, 2, 4, 6, 10, 14, 21, 28, 39, 51, 69, 86, 111, 138, 176, 214, 264, 315, 385, 454, 546, 641, 763, 881, 1032, 1188, 1385, 1580, 1824, 2066, 2371, 2668, 3037, 3413, 3869, 4310, 4846, 5387, 6045

Offset

1,2

Links

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

Example

For n = 4, the 6 possible sets are:
{1}, corresponding to 0111.
{1,2}, corresponding to 0011.
{1,3}, corresponding to 0101.
{1,4}, corresponding to 0110.
{1,2,3}, corresponding to 0001.
{1,2,3,4}, corresponding to 0000.

Prog

(Python)
from itertools import product
def ispal(w): return w == w[::-1]
def pls(w): return tuple(i for i in range(len(w)) if ispal(w[:i+1]))
def a(n):  # only search strings starting with 0 by symmetry
    return len(set(pls("0"+"".join(u)) for u in product("01", repeat=n-1)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Apr 03 2022

Crossrefs

Sequence in context: A280131 A082380 A238871 * A136460 A000065 A237758

Adjacent sequences: A323592 A323593 A323594 * A323596 A323597 A323598

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 18 2019

Extensions

a(23)-a(39) from Lars Blomberg, Feb 21 2019

Status

approved