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,4

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

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

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

Mathematica

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

Prog

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

Crossrefs

Column k=2 of A259776.

Cf. A112575, A183324, A260074.

Sequence in context: A109078 A291738 A321228 * A105543 A309352 A295618

Adjacent sequences: A033302 A033303 A033304 * A033306 A033307 A033308

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

New description from Max Alekseyev, Jul 09 2006

Status

approved