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

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

Author

Sergi Elizalde, Sep 10 2024

Keywords

• nonn

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

Examples

			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.
		

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.

Programs

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);

Formula

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.