A079992 Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=3, r=3, I={-2,2}.

1, 1, 2, 3, 9, 19, 49, 100, 233, 503, 1166, 2580, 5884, 13092, 29622, 66281, 149569, 335524, 755737, 1697149, 3819301, 8582469, 19306314, 43397191, 97600441, 219421360, 493425528, 1109386496, 2494606984, 5608933040, 12612101201

Offset

0,3

References

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.

Links

Table of n, a(n) for n=0..30.

Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135

Index entries for linear recurrences with constant coefficients, signature (1, 3, -1, 1, 1, 3, -5, -9, 1, 1, 1, -1, 1, 1).

Formula

a(n) = a(n-1) +3*a(n-2) -a(n-3) +a(n-4) +a(n-5) +3*a(n-6) -5*a(n-7) -9*a(n-8) +a(n-9) +a(n-10) +a(n-11) -a(n-12) +a(n-13) +a(n-14).

G.f.: -(x^2-1)*(x^6+x^4+x^3+x^2-1)/(x^14 +x^13 -x^12 +x^11 +x^10 +x^9 -9*x^8 -5*x^7 +3*x^6 +x^5 +x^4 -x^3 +3*x^2 +x-1)

Crossrefs

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

Sequence in context: A298357 A094812 A307898 * A324374 A106519 A006866

Adjacent sequences: A079989 A079990 A079991 * A079993 A079994 A079995

Keyword

nonn,easy

Author

Vladimir Baltic, Feb 17 2003

Status

approved