A241210 Number of binary strings of length n having a factorization as a concatenation of palindromes of length at least 2.

0, 2, 4, 6, 20, 32, 88, 162, 360, 758, 1564, 3290, 6692, 13898, 28356, 57954, 117948, 239378, 485472, 981374, 1982324, 3997004, 8051432, 16201164, 32570108, 65431734, 131358932, 263572810, 528600668, 1059691960, 2123635312, 4254511910, 8521368640, 17063718174, 34163130608

Offset

1,2

Links

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

Example

a(4) = 6 because {0000, 0011, 0110, 1001, 1100, 1111} are factorizable into palindromes of length >= 2.
Terms are even by symmetry. - Michael S. Branicky, Jul 28 2021

Prog

(Python)
from functools import lru_cache
def ispal(s): return s == s[::-1]
@lru_cache(maxsize=None)
def ok(b): # takes a binary string
    if len(b) >= 2 and ispal(b): return True
    for i in range(2, len(b)-1):
        if ispal(b[:i]) and ok(b[i:]): return True
    return False
def a(n): return 2*sum(1 for m in range(2**(n-1), 2**n) if ok(bin(m)[2:]))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jul 28 2021

Crossrefs

Cf. A241208, A241211.

Sequence in context: A108439 A245766 A193774 * A333992 A176652 A251724

Adjacent sequences: A241207 A241208 A241209 * A241211 A241212 A241213

Keyword

nonn,more

Author

Jeffrey Shallit, Apr 17 2014

Extensions

a(17)-a(30) from Giovanni Resta, Apr 18 2014

a(31)-a(35) from Michael S. Branicky, Jul 28 2021

Status

approved