A340314 Number of different possible profiles of palindromic length for prefixes of sequences of length n, over an arbitrary (unbounded) alphabet.

1, 2, 5, 11, 27, 63, 155, 376, 922, 2245, 5506

Offset

1,2

Comments

The palindromic length of a sequence is the minimum number of terms needed to write it as a concatenation of palindromes. For example, 011010 has palindromic length 3, as it can be written as (0110)(1)(0) or (0)(11)(010), but there is no way to write it as the concatenation of two palindromes.

The profile is the list of palindromic lengths of all prefixes. For 011010 it is (1,2,2,1,2,3). This sequence counts the distinct profiles, over all length-n sequences over an arbitrary (unbounded) alphabet.

Links

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

Anna E. Frid, Prefix palindromic length of the Thue-Morse word, arXiv:1906.09392 [cs.DM], 2019.

Prog

(Python)
from functools import lru_cache
from itertools import product
def ispal(w): return w == w[::-1]
@lru_cache(maxsize=None)
def pal_len(w):
  if len(w) <= 1: return len(w)
  return min(1+pal_len(w[i:]) for i in range(len(w), 0, -1) if ispal(w[:i]))
def plp(w): # palindrome length profile
  return tuple(pal_len(w[:i]) for i in range(1, len(w) + 1))
def a(n):  # only search strings starting with 0 by symmetry
  alphabet = [chr(c) for c in range(ord('0'), ord('0')+n)]
  return len(set(plp('0'+"".join(u)) for u in product(alphabet, repeat=n-1)))
print([a(n) for n in range(1, 8)])  # Michael S. Branicky, Jan 04 2021

Crossrefs

Cf. A340311.

Sequence in context: A266545 A095975 A006652 * A238825 A073225 A027087

Adjacent sequences: A340311 A340312 A340313 * A340315 A340316 A340317

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 04 2021

Status

approved