%I
%S 1,1,2,6,12,25,57,124,268,588,1285,2801,6118,13362,29168,63685,139057,
%T 303608,662888,1447352,3160121,6899745,15064810,32892270,71816436,
%U 156802881,342360937,747505396,1632091412,3563482500,7780451037,16987713169,37090703118,80983251898
%N Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.
%C Proof: Consider adding the letter n to a conforming (n1)permutation. The possible cases are: 1) (n1)perm  n; 2) (n2)perm  n  n1; 3) (n3)perm  n  n1  n2; 4) (n3)perm  n  n2  n1; 5) (n3)perm  n1  n  n2; and 6) (n4)perm  n1  n3  n n2; other cases are excluded by the rules. This yields a(n1)+a(n2)+3*a(n3)+a(n4) as the count of conforming npermutations with a(0)=1.
%C Partial sums calculated as follows:
%C p(i) 3 1 4 2 5
%C p(i)i 2 1 1 2 0
%C partial sum 2 1 2 0 0 // max = 2 so counted
%C p(i) 3 1 4 5 2
%C p(i)i 2 1 1 1 3
%C partial sum 2 1 2 3 0 // max = 3 so not counted
%C 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
%H Alois P. Heinz, <a href="/A214663/b214663.txt">Table of n, a(n) for n = 0..1000</a>
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao, Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,3,1).
%F G.f.: 1/(1xx^23*x^3x^4).
%e a(4) = 12: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214. The ten 4permutations starting with 4 or ending with 1, as well as 2413 and 3412, do not comply.
%p a:= n> (<<0100>, <0010>, <0001>, <1311>>^n)[4, 4]:
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jul 25 2012
%t CoefficientList[Series[1/(1  x  x^2  3 x^3  x^4), {x, 0, 37}], x]
%t LinearRecurrence[{1,1,3,1},{1,1,2,6},40] (* _Harvey P. Dale_, Apr 26 2019 *)
%Y Column k=3 of A276837.
%K nonn,easy
%O 0,3
%A _David Scambler_, Jul 24 2012
