

A214663


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


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Index entries for linear recurrences with constant coefficients, signature (1,1,3,1).


FORMULA

G.f.: 1/(1xx^23*x^3x^4).


EXAMPLE

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.


MAPLE

a:= n> (<<0100>, <0010>, <0001>, <1311>>^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



