|
%I #47 Jan 24 2022 07:04:26
%S 1,0,1,2,4,6,13,24,45,84,160,300,565,1064,2005,3774,7108,13386,25209,
%T 47472,89401,168360,317056,597080,1124425,2117520,3987721,7509690,
%U 14142276,26632782,50154949,94451976,177872293
%N Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.
%D Lehmer, D. H.; Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
%D R. P. Stanley, Enumerative Combinatorics I, p. 252, Example 4.7.16.
%H Alois P. Heinz, <a href="/A033305/b033305.txt">Table of n, a(n) for n = 0..1000</a>
%H Vladimir Kruchinin and D. V. Kruchinin, <a href="http://arxiv.org/abs/1103.2582">Composita and their properties </a>, arXiv:1103.2582 [math.CO], 2011-2013.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1,-1).
%F G.f.: (1-x)/((1+x)*(1 - 2*x + x^2 - 2*x^3 + x^4)).
%F a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) - a(n-5).
%F a(n) = h(n) - h(n-1), n>0, h(n) = Sum_{k=1..n} (Sum_{r=0..k} (C(k,r)*Sum_{m=0..r}(C(r,m)*Sum_{j=0..m} C(m,j)*C(j,n-m-k-j-r)*(-1)^(n-m-k-j-r) ))). - _Vladimir Kruchinin_, Sep 10 2010
%F Limit_{n -> infinity} a(n)/a(n-1) = (1 + sqrt(2) + sqrt(2*sqrt(2)-1)) /2 = 1.88320350591... for n>2. Limit_{n -> infinity} a(n-1)/a(n) = (1 + sqrt(2) - sqrt(2*sqrt(2)-1)) /2 = 0.53101005645... for n>0. - _Tim Monahan_, Aug 09 2011
%F 7*a(n) = 2*(-1)^n - 8*A112575(n) - 2*A112575(n-2) + 6*A112575(n-1) + 5*A112575(n+1). - _R. J. Mathar_, Sep 27 2013
%F Empirical: a(n) + a(n+1) = A183324(n). - _R. J. Mathar_, Sep 27 2013
%t LinearRecurrence[{1,1,1,1,-1},{1,0,1,2,4},40] (* _Harvey P. Dale_, Aug 28 2012 *)
%o (Maxima) h(n) := sum(sum(binomial(k,r) *sum(binomial(r,m) *sum(binomial(m,j) *binomial(j,n-m-k-j-r) *(-1)^(n-m-k-j-r), j,0,m), m,0,r), r,0,k), k,1,n); a(n):=h(n)-h(n-1); \\ _Vladimir Kruchinin_, Sep 10 2010
%o (Magma) I:=[1,0,1,2,4]; [n le 5 select I[n] else Self(n-1) +Self(n-2) +Self(n-3) +Self(n-4) -Self(n-5): n in [1..41]]; // _G. C. Greubel_, Jan 14 2022
%o (Sage) [( (1-x)/((1+x)*(1-2*x+x^2-2*x^3+x^4)) ).series(x,n+1).list()[n] for n in (0..40)] # _G. C. Greubel_, Jan 14 2022
%Y Column k=2 of A259776.
%Y Cf. A112575, A183324, A260074.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_
%E New description from _Max Alekseyev_, Jul 09 2006
|
