This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (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 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/(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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 18 02:20 EDT 2019. Contains 327149 sequences. (Running on oeis4.)