cp's OEIS Frontend

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

%I A001887 M3970 N1640 #55 Jan 31 2020 15:17:57
%S A001887 1,0,0,0,1,5,33,236,1918,17440,175649,1942171,23396353,305055960,
%T A001887 4280721564,64330087888,1030831875953,17545848553729,316150872317105,
%U A001887 6012076099604308,120330082937778554
%N A001887 Number of permutations p of {1,2,...,n} such that p(i) - i < 0 or p(i) - i > 2 for all i.
%C A001887 Previous name was: Hit polynomials.
%D A001887 J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)
%D A001887 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001887 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001887 Alois P. Heinz, <a href="/A001887/b001887.txt">Table of n, a(n) for n = 0..300</a>
%H A001887 E. R. Canfield, N. C. Wormald, <a href="https://doi.org/10.1016/0012-365X(87)90002-1">Menage numbers, bijections and P-recursiveness</a>, Discr. Math. 63 (1987) 117, table Section 7.
%H A001887 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 373
%H A001887 V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 224.
%H A001887 N. J. A. Sloane, <a href="/A001883/a001883_21.pdf">Annotated copy of Riordan's Three-Ply Staircase paper</a> (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963)
%H A001887 D. Zeilberger, <a href="http://arxiv.org/abs/1401.1089">Automatic Enumeration of Generalized Menage Numbers</a>, arXiv preprint arXiv:1401.1089 [math.CO], 2014.
%F A001887 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
%F A001887 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.
%F A001887 a(n) ~ exp(-3) * n!. - _Vaclav Kotesovec_, Sep 10 2014
%t A001887 nmax = 21;
%t A001887 gf = 1/(x^2-1)(x-Sum[n! (x(x-1)/(x^3-2x-1))^n + O[x]^nmax, {n, 0, nmax}]);
%t A001887 CoefficientList[gf, x] (* _Jean-François Alcover_, Aug 19 2018 *)
%Y A001887 Cf. A000255, A000271, A001883-A001891, A075851, A075852.
%Y A001887 First column of A080061.
%K A001887 nonn
%O A001887 0,6
%A A001887 _N. J. A. Sloane_
%E A001887 More terms from _Vladimir Baltic_ and _Vladeta Jovovic_, Jan 05 2003
%E A001887 New name from _Vaclav Kotesovec_ using a former comment by _Vladimir Baltic_ and _Vladeta Jovovic_, Sep 16 2014