A214663 Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.

1, 1, 2, 6, 12, 25, 57, 124, 268, 588, 1285, 2801, 6118, 13362, 29168, 63685, 139057, 303608, 662888, 1447352, 3160121, 6899745, 15064810, 32892270, 71816436, 156802881, 342360937, 747505396, 1632091412, 3563482500, 7780451037, 16987713169, 37090703118, 80983251898

Offset: 0

Author

David Scambler, Jul 24 2012

Keywords

• nonn
• easy

Comments

Proof: Consider adding the letter n to a conforming (n-1)-permutation. The possible cases are: 1) (n-1)-perm | n; 2) (n-2)-perm | n | n-1; 3) (n-3)-perm | n | n-1 | n-2; 4) (n-3)-perm | n | n-2 | n-1; 5) (n-3)-perm | n-1 | n | n-2; and 6) (n-4)-perm | n-1 | n-3 | n |n-2; other cases are excluded by the rules. This yields a(n-1)+a(n-2)+3*a(n-3)+a(n-4) as the count of conforming n-permutations with a(0)=1.

Partial sums calculated as follows:

p(i) 3 1 4 2 5

p(i)-i 2 -1 1 -2 0

partial sum 2 1 2 0 0 // max = 2 so counted

p(i) 3 1 4 5 2

p(i)-i 2 -1 1 1 -3

partial sum 2 1 2 3 0 // max = 3 so not counted

Number of permutations of length n>=0 avoiding the partially ordered pattern (POP) {1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the last element. - Sergey Kitaev, Dec 08 2020

Examples

			a(4) = 12: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214. The ten 4-permutations starting with 4 or ending with 1, as well as 2413 and 3412, do not comply.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
• László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 1 at p. 3.
• Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
• Index entries for linear recurrences with constant coefficients, signature (1,1,3,1).

Crossrefs

Column k=3 of A276837.

Programs

Maple

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|3|1|1>>^n)[4, 4]:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 25 2012

Mathematica

CoefficientList[Series[1/(1 - x - x^2 - 3 x^3 - x^4), {x, 0, 37}], x]
LinearRecurrence[{1,1,3,1},{1,1,2,6},40] (* Harvey P. Dale, Apr 26 2019 *)

Formula

G.f.: 1/(1-x-x^2-3*x^3-x^4).