A033305 Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

1, 0, 1, 2, 4, 6, 13, 24, 45, 84, 160, 300, 565, 1064, 2005, 3774, 7108, 13386, 25209, 47472, 89401, 168360, 317056, 597080, 1124425, 2117520, 3987721, 7509690, 14142276, 26632782, 50154949, 94451976, 177872293

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• 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.
• R. P. Stanley, Enumerative Combinatorics I, p. 252, Example 4.7.16.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,-1).

Crossrefs

Column k=2 of A259776.

Cf. A112575, A183324, A260074.

Programs

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

Mathematica

LinearRecurrence[{1,1,1,1,-1},{1,0,1,2,4},40] (* Harvey P. Dale, Aug 28 2012 *)

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 */

SageMath

[( (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

Formula

G.f.: (1-x)/((1+x)*(1 - 2*x + x^2 - 2*x^3 + x^4)).

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) - a(n-5).

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

Limit_{n -> oo} a(n)/a(n-1) = (1 + sqrt(2) + sqrt(2*sqrt(2)-1)) /2 = 1.88320350591... for n>2. Limit_{n -> oo} a(n-1)/a(n) = (1 + sqrt(2) - sqrt(2*sqrt(2)-1)) /2 = 0.53101005645... for n>0. - Tim Monahan, Aug 09 2011

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

Empirical: a(n) + a(n+1) = A183324(n). - R. J. Mathar, Sep 27 2013

Extensions

New description from Max Alekseyev, Jul 09 2006