A001887 Number of permutations p of {1,2,...,n} such that p(i) - i < 0 or p(i) - i > 2 for all i. (Formerly M3970 N1640)

1, 0, 0, 0, 1, 5, 33, 236, 1918, 17440, 175649, 1942171, 23396353, 305055960, 4280721564, 64330087888, 1030831875953, 17545848553729, 316150872317105, 6012076099604308, 120330082937778554

Offset

0,6

Comments

Previous name was: Hit polynomials.

References

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

E. R. Canfield, N. C. Wormald, Menage numbers, bijections and P-recursiveness, Discr. Math. 63 (1987) 117, table Section 7.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 224.

N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963)

D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Formula

G.f.: (1/(x^2-1))*(x-Sum_{n>=0} n!*(x*(x-1)/(x^3-2*x-1))^n). - Vladeta Jovovic, Jun 30 2007

D-finite with recurrence (P. Flajolet, 1997): a(n) = (n-1)*a(n-1) + (n+2)*a(n-2) - (3*n-13)*a(n-3) - (2*n-8)*a(n-4) + (3*n-15)*a(n-5) + (n-4)*a(n-6) - (n-7)*a(n-7) - a(n-8), n>8.

a(n) ~ exp(-3) * n!. - Vaclav Kotesovec, Sep 10 2014

Mathematica

nmax = 21;
gf = 1/(x^2-1)(x-Sum[n! (x(x-1)/(x^3-2x-1))^n + O[x]^nmax, {n, 0, nmax}]);
CoefficientList[gf, x] (* Jean-François Alcover, Aug 19 2018 *)

Crossrefs

Cf. A000255, A000271, A001883-A001891, A075851, A075852.

First column of A080061.

Sequence in context: A128418 A335119 A284733 * A118803 A284734 A093427

Adjacent sequences: A001884 A001885 A001886 * A001888 A001889 A001890

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Vladimir Baltic and Vladeta Jovovic, Jan 05 2003

New name from Vaclav Kotesovec using a former comment by Vladimir Baltic and Vladeta Jovovic, Sep 16 2014

Status

approved