A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.
0, 4, 6, 14, 26, 48, 86, 148, 232, 400, 622, 982, 1514, 2440, 3482, 5680, 8162, 12932, 18398, 29146, 40706, 64856, 90070, 141880, 196448, 309712, 425412, 668978, 917450, 1437148, 1966022, 3074080, 4192882, 6545344, 8912278, 13877920, 18874298, 29341624, 39842594, 61835140, 83886002, 129977116, 176160686, 272563362
Offset: 1
Keywords
Links
- Michael S. Branicky, Table of n, a(n) for n = 1..6617
- Michael S. Branicky, Python program for A370410 (bitwise operations)
- Michael S. Branicky, Python program for A370410 (explicit construction)
- R. C. Lyndon and M. P. Schützenberger, The equation a^M = b^N c^P in a free group, Michigan Math. J., 9(4):289-298, 1962.
Programs
-
Python
# see below and Links for faster programs from itertools import product def p(w): return w == w[::-1] def c(w): return any(p(w[:i]) and p(w[i:]) for i in range(1, len(w))) def a(n): return 2*sum(1 for w in product("01", repeat=n-1) if c(("1",)+w)) print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024 -
Python
from itertools import product def bin_pals(d): yield from ("".join(p+(m,)+p[::-1]) for p in product("01", repeat=d//2) for m in [[""], ["0", "1"]][d%2]) def a(n): return len(set(a+b for i in range(1, n) for a in bin_pals(i) for b in bin_pals(n-i))) print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024 -
Python
# uses formula above; functions/imports in A007055, A056458 def a(n): return A007055(n) - A056458(n) print([a(n) for n in range(1, 45)]) # Michael S. Branicky, Feb 21 2024
Formula
From Daniel Gabric, Feb 21 2024: (Start)
Proof of the above formula: Let w be a length-n binary string that is the concatenation of two possibly empty palindromes. It suffices to show that w is not the concatenation of two nonempty palindromes iff w is a primitive palindrome.
We prove the forward direction. Suppose w is not the concatenation of two nonempty palindromes. By assumption, w is the concatenation of two possibly empty palindromes. Therefore, w must be a palindrome. Suppose, for the sake of a contradiction, that w is not primitive. Then w = z^i for some nonempty string z and some integer i>=2. But since w is a palindrome, we have that z^i = w = w^R = (z^i)^R = (z^R)^i, which implies z is a palindrome. Thus, w is the concatenation of the nonempty palindromes z and z^(i-1), a contradiction.
Now we prove the backward direction. Assume, for the sake of a contradiction, that w is a primitive palindrome, and w = uv for some nonempty palindromes u and v. Then uv = w = w^R = (uv)^R = v^Ru^R = vu. By Lemma 3 in a paper of Lyndon and Schützenberger (see links for reference), uv = vu implies w is not primitive, a contradiction. (End)
Extensions
a(21)-a(44) from Michael S. Branicky, Feb 18 2024
Comments