A079990 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={-1,2}.

1, 1, 1, 2, 6, 16, 36, 73, 157, 353, 797, 1776, 3916, 8636, 19145, 42504, 94286, 208948, 462907, 1025863, 2274069, 5040891, 11173063, 24763854, 54886846, 121655063, 269646786, 597664017, 1324697483, 2936135519, 6507831521, 14424377636

Offset

0,4

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

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

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

Formula

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

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

Crossrefs

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

Sequence in context: A352066 A351971 A365245 * A127902 A157136 A178523

Adjacent sequences: A079987 A079988 A079989 * A079991 A079992 A079993

Keyword

nonn

Author

Vladimir Baltic, Feb 17 2003

Status

approved