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

%I #35 May 15 2019 08:33:37

%S 1,2,6,18,46,115,301,792,2068,5380,14020,36581,95413,248786,648714,

%T 1691686,4411530,11503991,29998953,78228640,203998184,531969064,

%U 1387222648,3617479225,9433351129,24599481138,64148406350,167280683834

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

%H R. H. Hardin, <a href="/A072827/b072827.txt">Table of n, a(n) for n = 1..400</a>

%H Vladimir Baltic, <a href="https://doi.org/10.2298/AADM1000008B">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135.

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,3,5,6,-1,-1,0,-1,-1).

%F 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).

%F 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]

%t 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 *)

%o (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

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

%K nonn,easy

%O 1,2

%A _Vladimir Baltic_, Jul 21 2002