login
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)
3
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
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
First column of A080061.
Sequence in context: A128418 A335119 A284733 * A118803 A284734 A093427
KEYWORD
nonn
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