OFFSET
0,4
COMMENTS
Equivalently, a(n) is the number of permutations of {1,2,...,n} that have no proper Hertzsprung bifix (i.e., a prefix and a suffix of length i<n that form the same pattern, with one consisting of the smallest i entries and the other consisting of the largest i entries of the permutation).
LINKS
Miklós Bóna, Where the monotone pattern (mostly) rules, Discrete Math. 308 (2008), no. 23, 5782-5788.
Anders Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebraic Combinatorics 5 (2022), 1257-1277.
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.
FORMULA
a(n) = n! - Sum_{i=1..floor(n/2)} (i! + a(i))*(n-2*i)!.
EXAMPLE
For n=4, the a(4) = 18 non-self-overlapping permutations of {1,2,3,4} are all but 1234, 4321, 1324, 4231, 2143, 3412.
MAPLE
NonOverPerms:= proc(n) option remember;
n!-add((i! + NonOverPerms(i))*(n-2*i)!, i=1..floor(n/2))
end:
seq(NonOverPerms(n), n=0..25);
CROSSREFS
KEYWORD
nonn
AUTHOR
Sergi Elizalde, Sep 10 2024
STATUS
approved