A241211 Number of binary strings of length n having exactly one factorization as a concatenation of palindromes of length >= 2.

0, 2, 4, 4, 18, 22, 64, 96, 188, 388, 648, 1248, 2040, 3784, 6544, 11162, 19356, 32396, 55768, 93678, 157308, 263308, 438512, 731198, 1211304, 2004076, 3306552, 5445588, 8955544, 14690980, 24061172, 39360032

Offset

1,2

Comments

Terms are even by symmetry. - Michael S. Branicky, Jul 28 2021

Links

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

Example

a(4) = 4, because {0011, 0110, 1001, 1100} have unique factorizations into palindromes of length >= 2.

Prog

(Python)
from functools import lru_cache
from itertools import product
def ispal(s): return s == s[::-1]
@lru_cache(maxsize=None)
def f(b): # factorizations of binary string b
    factorizations = int(len(b) >= 2 and ispal(b))
    for i in range(2, len(b)-1):
        factorizations += ispal(b[:i]) * f(b[i:])
        if factorizations >= 2: return 2 # short circuit on condition
    return factorizations
def a(n):
    return 2*sum(f("0"+"".join(b))==1 for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jul 28 2021

Crossrefs

Cf. A241208, A241210.

Sequence in context: A088042 A013140 A326773 * A155720 A230694 A155725

Adjacent sequences: A241208 A241209 A241210 * A241212 A241213 A241214

Keyword

nonn,more

Author

Jeffrey Shallit, Apr 17 2014

Extensions

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

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

Status

approved