The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #141 Dec 06 2024 11:39:36
%S 1,1,2,2,4,4,7,7,11,12,18,17,25,27,38,38,50,51,70,69,92,95,122,118,
%T 151,156,197,195,244,242,305,297,369,376,456,441,536,541,658,643,767,
%U 761,920,895,1074,1079,1271,1227,1444,1436,1696,1665,1948,1923,2258,2190
%N Number of distinct sets of palindrome prefix lengths, over all binary palindromes of length n.
%C Claesson's conjecture: for n>=3, a(n+1) equals the number of Wilf-classes of Hertzsprung patterns of length n. These patterns correspond to "rigid patterns" from Myers's work. Bóna studied them under the name "very tight patterns". The number of Wilf-classes of Hertzsprung patterns can also be interpreted as the number of different autocorrelation polynomials of self-overlapping permutations. For more details, definitions and examples, see works by Claesson, Bóna, Kirgizov-Nurligareev and Myers in the links section. - _Sergey Kirgizov_, Nov 28 2024
%H Michael S. Branicky, <a href="/A304178/b304178.txt">Table of n, a(n) for n = 1..64</a>
%H Miklós Bóna, <a href="https://doi.org/10.1016/j.disc.2007.10.030">Where the monotone pattern (mostly) rules</a>, Discrete mathematics, 308(23), 2008.
%H Anders Claesson, <a href="https://doi.org/10.5802/alco.202">From Hertzsprung's problem to pattern-rewriting systems</a>, Algebraic Combinatorics, 5(6), 2022.
%H Anders Claesson, <a href="https://www.math.ntnu.no/acpms/view_talk.html?id=126">On the problem of Hertzsprung and similar problems (pdf slides and video)</a>, Seminar "Algebraic and combinatorial perspectives in the mathematical sciences", 2022.
%H Sergey Kirgizov, Khaydar Nurligareev, <a href="https://arxiv.org/abs/2311.11677">Asymptotics of self-overlapping permutations</a>, arXiv:2311.11677 [math.CO], 2023-2024.
%H Amy N. Myers, <a href="https://doi.org/10.1006/jcta.2002.3279">Counting permutations by their rigid patterns</a>, J. Combin. Theory Ser. A 99(2), 2002.
%e For n = 7, the possible sets are:
%e {1,2,3,4,5,6,7} for the string 0000000,
%e {1,3,5,7} for the string 0101010,
%e {1,2,3,7} for the string 0001000,
%e {1,2,7} for the string 0010100,
%e {1,3,7} for the string 0100010,
%e {1,4,7} for the string 0110110,
%e {1,7} for the string 0111110.
%o (Python)
%o from itertools import product
%o def pals(n):
%o for p in product("01", repeat=n//2):
%o left = "".join(p)
%o right = left[::-1]
%o if n%2==0: yield left+right
%o else:
%o yield left+"0"+right
%o yield left+"1"+right
%o def pal_prefix_lengths(s): # skip length 1 since it is in all sets
%o return [i for i in range(2, len(s)+1) if s[:i]==(s[:i])[::-1]]
%o def a(n):
%o sets = set()
%o for p in pals(n):
%o if p[0]=="1": break # skip by symmetry
%o sets.add(tuple(pal_prefix_lengths(p)))
%o return len(sets)
%o print([a(n) for n in range(1,41)]) # _Michael S. Branicky_, Dec 05 2020
%K nonn
%O 1,3
%A _Jeffrey Shallit_, Jan 28 2019
%E a(41) and beyond from _Michael S. Branicky_, Dec 05 2020