A079981 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,0,1,2}.

1, 0, 0, 0, 1, 0, 2, 0, 3, 0, 8, 0, 12, 0, 27, 0, 52, 0, 95, 0, 196, 0, 369, 0, 720, 0, 1408, 0, 2709, 0, 5292, 0, 10249, 0, 19894, 0, 38675, 0, 74992, 0, 145692, 0, 282823, 0, 549000, 0, 1066095, 0, 2069496, 0, 4018065, 0, 7801024, 0, 15144960, 0, 29404281, 0

Offset

0,7

Comments

Also, 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,-1,0,2}. a(n)=A079980(k) if n=2k, a(n)=0 otherwise.

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

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 (0,0,0,1,0,4,0,2,0,2,0,-2,0,1,0,0,0,1).

Formula

Recurrence: a(n) = a(n-4)+4*a(n-6)+2*a(n-8)+2*a(n-10)-2*a(n-12)+a(n-14)+a(n-18).

G.f.: -(x^12-2*x^6+1)/(x^18+x^14-2*x^12+2*x^10+2*x^8+4*x^6+x^4-1).

Mathematica

LinearRecurrence[{0, 0, 0, 1, 0, 4, 0, 2, 0, 2, 0, -2, 0, 1, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 2, 0, 3, 0, 8, 0, 12, 0, 27, 0, 52, 0}, 80] (* Harvey P. Dale, Aug 18 2012 *)

Crossrefs

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

Bisection gives A079980 (even part).

Sequence in context: A317443 A308218 A067165 * A117776 A298610 A186492

Adjacent sequences: A079978 A079979 A079980 * A079982 A079983 A079984

Keyword

nonn,easy

Author

Vladimir Baltic, Feb 17 2003

Status

approved