A080000 - OEIS

%I #12 Jul 29 2024 10:43:00

%S 1,1,1,1,1,2,3,5,7,9,12,16,24,35,50,70,96,135,190,270,383,539,759,

%T 1065,1500,2116,2985,4212,5932,8356,11770,16585,23381,32953,46445,

%U 65445,92216,129951,183129,258091,363719,512566,722316,1017886,1434445,2021476

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

%D 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.

%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">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, 0, 0, 0, 2, -1, 1, 0, 0, -1).

%F G.f.: -(x^5-1)/(x^10-x^7+x^6-2*x^5-x+1).

%F a(n) = a(n-1)+2*a(n-5)-a(n-6)+a(n-7)-a(n-10).

%e G.f. = 1 + x + x^2 + x^3 + x^4 + 2*x^5 + 3*x^6 + 5*x^7 + 7*x^8 + 9*x^9 + ...

%e a(5) = 2 for permutations [1,2,3,4,5] and [4,5,1,2,3].

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

%K nonn

%O 0,6

%A _Vladimir Baltic_, Feb 10 2003