login
Number of binary strings of length 2n having exactly 1 factorization as a concatenation of one or more even-length palindromes.
4

%I #20 Jul 28 2021 14:03:31

%S 2,4,12,36,96,288,836,2412,7000,20404,59256,172236,500776,1455908,

%T 4232288,12305028

%N Number of binary strings of length 2n having exactly 1 factorization as a concatenation of one or more even-length palindromes.

%C Terms are even by symmetry. - _Michael S. Branicky_, Jul 28 2021

%e a(2) = 4, since the only strings of length 4 with unique factorization are {0011, 0110, 1001, 1100}.

%o (Python)

%o from functools import lru_cache

%o from itertools import product

%o def ispal(s): return s == s[::-1]

%o @lru_cache(maxsize=2*10**7)

%o def f(b): # factorizations of binary string b

%o factorizations = int(len(b) >= 2 and ispal(b))

%o for i in range(2, len(b)-1, 2):

%o factorizations += ispal(b[:i]) * f(b[i:])

%o if factorizations >= 2: return 2 # short circuit on condition

%o return factorizations

%o def a(n):

%o return 2*sum(f("0"+"".join(b))==1 for b in product("01", repeat=2*n-1))

%o print([a(n) for n in range(1, 11)]) # _Michael S. Branicky_, Jul 28 2021

%Y Cf. A241210, A241211.

%K nonn,more

%O 1,1

%A _Jeffrey Shallit_, Apr 17 2014

%E a(10)-a(16) from _Giovanni Resta_, Apr 18 2014