cp's OEIS Frontend

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

%I A214663 #57 May 19 2023 11:00:59
%S A214663 1,1,2,6,12,25,57,124,268,588,1285,2801,6118,13362,29168,63685,139057,
%T A214663 303608,662888,1447352,3160121,6899745,15064810,32892270,71816436,
%U A214663 156802881,342360937,747505396,1632091412,3563482500,7780451037,16987713169,37090703118,80983251898
%N A214663 Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.
%C A214663 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.
%C A214663 Partial sums calculated as follows:
%C A214663   p(i)         3  1  4  2  5
%C A214663   p(i)-i       2 -1  1 -2  0
%C A214663   partial sum  2  1  2  0  0 // max = 2 so counted
%C A214663   p(i)         3  1  4  5  2
%C A214663   p(i)-i       2 -1  1  1 -3
%C A214663   partial sum  2  1  2  3  0 // max = 3 so not counted
%C A214663 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 A214663 Alois P. Heinz, <a href="/A214663/b214663.txt">Table of n, a(n) for n = 0..1000</a>
%H A214663 Alice L. L. Gao and 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 A214663 Alice L. L. Gao and 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 A214663 László Németh and Dragan Stevanović, <a href="https://www.researchgate.net/publication/370765824_Graph_solution_of_system_of_recurrence_equations">Graph solution of system of recurrence equations</a>, Research Gate, 2023. See Table 1 at p. 3.
%H A214663 Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, <a href="https://arxiv.org/abs/2101.12061">Permutations Avoiding Certain Partially-ordered Patterns</a>, arXiv:2101.12061 [math.CO], 2021.
%H A214663 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,3,1).
%F A214663 G.f.: 1/(1-x-x^2-3*x^3-x^4).
%e A214663 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.
%p A214663 a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|3|1|1>>^n)[4, 4]:
%p A214663 seq(a(n), n=0..40);  # _Alois P. Heinz_, Jul 25 2012
%t A214663 CoefficientList[Series[1/(1 - x - x^2 - 3 x^3 - x^4), {x, 0, 37}], x]
%t A214663 LinearRecurrence[{1,1,3,1},{1,1,2,6},40] (* _Harvey P. Dale_, Apr 26 2019 *)
%Y A214663 Column k=3 of A276837.
%K A214663 nonn,easy
%O A214663 0,3
%A A214663 _David Scambler_, Jul 24 2012