login
Number of permutations of {1,2,...,n} that are non-self-overlapping as Hertzsprung patterns; also called non-extendible.
0

%I #17 Sep 12 2024 07:49:22

%S 1,1,0,4,18,106,658,4778,38770,352458,3546170,39179282,471653322,

%T 6146403266,86212578962,1295136607114,20747437026442,353059209467042,

%U 6360348815730370,120931046165866362,2420054522391186274,50846927248165344442,1119121906010637564906,25749587951077654272898

%N Number of permutations of {1,2,...,n} that are non-self-overlapping as Hertzsprung patterns; also called non-extendible.

%C 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).

%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 Math. 308 (2008), no. 23, 5782-5788.

%H Anders Claesson, <a href="https://doi.org/10.5802/alco.202">From Hertzsprung’s problem to pattern-rewriting systems</a>, Algebraic Combinatorics 5 (2022), 1257-1277.

%H A. N. Myers, <a href="https://doi.org/10.1006/jcta.2002.3279">Counting permutations by their rigid patterns</a>, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.

%F a(n) = n! - Sum_{i=1..floor(n/2)} (i! + a(i))*(n-2*i)!.

%e 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.

%p NonOverPerms:= proc(n) option remember;

%p n!-add((i! + NonOverPerms(i))*(n-2*i)!, i=1..floor(n/2))

%p end:

%p seq(NonOverPerms(n), n=0..25);

%K nonn

%O 0,4

%A _Sergi Elizalde_, Sep 10 2024