login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 22 11:17 EDT 2021. Contains 345375 sequences. (Running on oeis4.)