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,3

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

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

Formula

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

Example

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.

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

Crossrefs

Column k=3 of A276837.

Sequence in context: A238462 A099495 A232164 * A151385 A034875 A136515

Adjacent sequences: A214660 A214661 A214662 * A214664 A214665 A214666

Keyword

nonn,easy

Author

David Scambler, Jul 24 2012

Status

approved