login
A376110
Number of permutations of {1,2,...,n} that are non-self-overlapping as Hertzsprung patterns; also called non-extendible.
0
1, 1, 0, 4, 18, 106, 658, 4778, 38770, 352458, 3546170, 39179282, 471653322, 6146403266, 86212578962, 1295136607114, 20747437026442, 353059209467042, 6360348815730370, 120931046165866362, 2420054522391186274, 50846927248165344442, 1119121906010637564906, 25749587951077654272898
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
Sequence in context: A007711 A321278 A020114 * A354015 A009597 A241841
KEYWORD
nonn
AUTHOR
Sergi Elizalde, Sep 10 2024
STATUS
approved