A072827 Number of permutations satisfying i-2<=p(i)<=i+3, i=1..n.

1, 2, 6, 18, 46, 115, 301, 792, 2068, 5380, 14020, 36581, 95413, 248786, 648714, 1691686, 4411530, 11503991, 29998953, 78228640, 203998184, 531969064, 1387222648, 3617479225, 9433351129, 24599481138, 64148406350, 167280683834

Offset: 1

Author

Vladimir Baltic, Jul 21 2002

Keywords

• nonn
• easy

Links

• R. H. Hardin, Table of n, a(n) for n = 1..400
• Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135.
• Index entries for linear recurrences with constant coefficients, signature (1,2,3,5,6,-1,-1,0,-1,-1).

Crossrefs

Cf. A002524, A002525, A002526, A002527, A002528, A002529, A072850, A072851, A072852, A072853, A072854, A072855, A072856, A079955-A080014.

Programs

Mathematica

LinearRecurrence[{1,2,3,5,6,-1,-1,0,-1,-1},{1,2,6,18,46,115,301,792,2068,5380},30] (* Harvey P. Dale, Aug 15 2014 *)

PARI

a(n)=([0,1,0,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0,0; 0,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,1,0,0,0,0; 0,0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,0,1; -1,-1,0,-1,-1,6,5,3,2,1]^(n-1)*[1;2;6;18;46;115;301;792;2068;5380])[1,1] \\ Charles R Greathouse IV, Jul 28 2015

Formula

Recurrence: a(n) = a(n-1)+2*a(n-2)+3*a(n-3)+5*a(n-4)+6*a(n-5)-a(n-6)-a(n-7)-a(n-9)-a(n-10).

G.f.: (1-x^5-x^3-x^2)/(x^10+x^9+x^7+x^6-6*x^5-5*x^4-3*x^3-2*x^2-x+1). [Corrected by Georg Fischer, May 15 2019]