login
A241208
Number of binary strings of length 2n having exactly 1 factorization as a concatenation of one or more even-length palindromes.
4
2, 4, 12, 36, 96, 288, 836, 2412, 7000, 20404, 59256, 172236, 500776, 1455908, 4232288, 12305028
OFFSET
1,1
COMMENTS
Terms are even by symmetry. - Michael S. Branicky, Jul 28 2021
EXAMPLE
a(2) = 4, since the only strings of length 4 with unique factorization are {0011, 0110, 1001, 1100}.
PROG
(Python)
from functools import lru_cache
from itertools import product
def ispal(s): return s == s[::-1]
@lru_cache(maxsize=2*10**7)
def f(b): # factorizations of binary string b
factorizations = int(len(b) >= 2 and ispal(b))
for i in range(2, len(b)-1, 2):
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=2*n-1))
print([a(n) for n in range(1, 11)]) # Michael S. Branicky, Jul 28 2021
CROSSREFS
Sequence in context: A202727 A325255 A084716 * A149837 A149838 A192236
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Apr 17 2014
EXTENSIONS
a(10)-a(16) from Giovanni Resta, Apr 18 2014
STATUS
approved