OFFSET
1,3
COMMENTS
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
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..64
Miklós Bóna, Where the monotone pattern (mostly) rules, Discrete mathematics, 308(23), 2008.
Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, Algebraic Combinatorics, 5(6), 2022.
Anders Claesson, On the problem of Hertzsprung and similar problems (pdf slides and video), Seminar "Algebraic and combinatorial perspectives in the mathematical sciences", 2022.
Sergey Kirgizov, Khaydar Nurligareev, Asymptotics of self-overlapping permutations, arXiv:2311.11677 [math.CO], 2023-2024.
Amy N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory Ser. A 99(2), 2002.
EXAMPLE
For n = 7, the possible sets are:
{1,2,3,4,5,6,7} for the string 0000000,
{1,3,5,7} for the string 0101010,
{1,2,3,7} for the string 0001000,
{1,2,7} for the string 0010100,
{1,3,7} for the string 0100010,
{1,4,7} for the string 0110110,
{1,7} for the string 0111110.
PROG
(Python)
from itertools import product
def pals(n):
for p in product("01", repeat=n//2):
left = "".join(p)
right = left[::-1]
if n%2==0: yield left+right
else:
yield left+"0"+right
yield left+"1"+right
def pal_prefix_lengths(s): # skip length 1 since it is in all sets
return [i for i in range(2, len(s)+1) if s[:i]==(s[:i])[::-1]]
def a(n):
sets = set()
for p in pals(n):
if p[0]=="1": break # skip by symmetry
sets.add(tuple(pal_prefix_lengths(p)))
return len(sets)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Dec 05 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 28 2019
EXTENSIONS
a(41) and beyond from Michael S. Branicky, Dec 05 2020
STATUS
approved