login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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]

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 24 18:18 EDT 2017. Contains 286997 sequences.