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
KEYWORD
nonn,easy
AUTHOR
David Scambler, Jul 24 2012
STATUS
approved