|
%I #57 May 19 2023 11:00:59
%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 (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 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 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 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 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 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 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,3,1).
%F G.f.: 1/(1-x-x^2-3*x^3-x^4).
%e 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 a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|3|1|1>>^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
|
