A001887 Number of permutations p of {1,2,...,n} such that p(i) - i < 0 or p(i) - i > 2 for all i.
1, 0, 0, 0, 1, 5, 33, 236, 1918, 17440, 175649, 1942171, 23396353, 305055960, 4280721564, 64330087888, 1030831875953, 17545848553729, 316150872317105, 6012076099604308, 120330082937778554
Offset: 0
Keywords
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.
Programs
-
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 *)
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
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
Comments