cp's OEIS Frontend

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

%I A376110 #17 Sep 12 2024 07:49:22
%S A376110 1,1,0,4,18,106,658,4778,38770,352458,3546170,39179282,471653322,
%T A376110 6146403266,86212578962,1295136607114,20747437026442,353059209467042,
%U A376110 6360348815730370,120931046165866362,2420054522391186274,50846927248165344442,1119121906010637564906,25749587951077654272898
%N A376110 Number of permutations of {1,2,...,n} that are non-self-overlapping as Hertzsprung patterns; also called non-extendible.
%C A376110 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 A376110 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 A376110 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 A376110 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 A376110 a(n) = n! - Sum_{i=1..floor(n/2)} (i! + a(i))*(n-2*i)!.
%e A376110 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 A376110 NonOverPerms:= proc(n) option remember;
%p A376110   n!-add((i! + NonOverPerms(i))*(n-2*i)!, i=1..floor(n/2))
%p A376110 end:
%p A376110 seq(NonOverPerms(n), n=0..25);
%K A376110 nonn
%O A376110 0,4
%A A376110 _Sergi Elizalde_, Sep 10 2024