A001883 -id:A001883 - 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.

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

Offset: 0

N. J. A. Sloane

nonn

Previous name was: Hit polynomials.

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).

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.

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

First column of A080061.

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 *)

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

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

A292574 Number of permutations p of {1,2,...,n} such that p(i)-i not in {-1,0,1,2}.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 6, 58, 499, 4814, 50284, 572228, 7050770, 93637691, 1334156612, 20308818956, 329025006637, 5653813150732, 102722614426328, 1967763318700136, 39640921470181124, 837836538203311613, 18539041315706787978, 428620090892592760870

Offset: 0

Andrew Howroyd, Sep 19 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..40
D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Cf. A000271, A001883, A270174.

A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.

Original entry on oeis.org

0, 0, 1, 2, 8, 40, 236, 1648, 13125, 117794, 1175224, 12903874, 154615096, 2007498192, 28075470833, 420753819282, 6726830163592, 114278495205524, 2055782983578788, 39039148388975552, 780412763620655061, 16381683795665956242, 360258256118419518680, 8283042472303599966974

Offset: 0

Alois P. Heinz, Jan 21 2019

nonn

			a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
a(5) = 40: 21453, 21534, 23154, 23451, 23514, 24153, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34152, 34251, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45132, 45213, 45231, 51234, 51423, 51432, 53124, 53214, 53412, 53421, 54132, 54213, 54231.

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

Column k=1 of A299789.

Cf. A000142, A000166, A001883, A002467, A016933, A047252, A323671.

b:= proc(s, k) option remember; (n-> `if`(n=0, `if`(k=1, 1, 0), add(
      `if`(n=j, 0, b(s minus {j}, min(k, abs(n-j)))), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}, n):
seq(a(n), n=0..14);
# second Maple program:
a:= n-> (f-> f(1)-f(2))(k-> `if`(n=0, 1, LinearAlgebra[Permanent](
        Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))):
seq(a(n), n=0..14);
# third Maple program:
g:= proc(n) g(n):= `if`(n<2, 1-n, (n-1)*(g(n-1)+g(n-2))) end:
h:= proc(n) h(n):= `if`(n<7, [1, 0$3, 1, 4, 29][n+1], n*h(n-1)+4*h(n-2)
      -3*(n-3)*h(n-3)+(n-4)*h(n-4)+2*(n-5)*h(n-5)-(n-7)*h(n-6)-h(n-7))
    end:
a:= n-> g(n)-h(n):
seq(a(n), n=0..25);

g[n_] := g[n] = If[n < 2, 1-n, (n-1)(g[n-1] + g[n-2])];
h[n_] := h[n] = If[n < 7, {1, 0, 0, 0, 1, 4, 29}[[n+1]],
     n h[n-1] + 4h[n-2] - 3(n-3)h[n-3] + (n-4)h[n-4] +
     2(n-5)h[n-5] - (n-7)h[n-6] - h[n-7]];
a[n_] := g[n] - h[n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after third Maple program *)

a(n) = A000142(n) - A001883(n) - A002467(n).
a(n) = A000166(n) - A001883(n).
a(n) = Sum_{k=1..n} A323671(n,k).
a(n) is odd <=> n in { A016933 }.
a(n) is even <=> n in { A047252 }.

A001884 Hit polynomials.

Original entry on oeis.org

1, 0, 1, 2, 20, 104, 775, 6140, 55427, 553802, 6087992, 72994152, 948103477, 13262133736, 198769630061, 3177862894922, 53984653965996, 971068821144112, 18438722595913195, 368558842844143268, 7735520783692157215, 170095060428041137778, 3910332719957508452016, 93806427360751009531632

Offset: 1

N. J. A. Sloane

nonn

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).

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

Second column of A080018.

Cf. A001883-A001891.

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

a(21)-a(24) from Vaclav Kotesovec, Oct 10 2017

A001890 Hit polynomials.

Original entry on oeis.org

1, 10, 34, 206, 1351, 10543, 92708, 912884, 9917445, 117838808, 1519483258, 21128310078, 315093762147, 5016410089130, 84909414423784, 1522548805068310, 28830824064870329, 574880701875755325, 12039866150973004846, 264230694283295736788, 6063848537910027941323

Offset: 3

N. J. A. Sloane

nonn

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).

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

Fourth column of A080061.

Cf. A001883-A001891.

(* Program not suitable to compute more than a dozen terms *)
M[n_] := Table[If[0 <= i - j <= 2, x, 1], {i, 1, n}, {j, 1, n}];
a[n_] := Coefficient[Permanent[M[n]], x, 3];
Table[an = a[n]; Print[n, " ", an]; an, {n, 3, 15}] (* Jean-François Alcover, Jan 12 2018 *)

More terms from Vladeta Jovovic, Vladimir Baltic, Jan 23 2003

a(21)-a(23) from Vaclav Kotesovec, Oct 10 2017

A078509 Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.

Original entry on oeis.org

1, 1, 1, 1, 5, 23, 131, 883, 6859, 60301, 591605, 6405317, 75843233, 974763571, 13512607303, 200949508327, 3190881283415, 53880906258521, 964039575154409, 18217997734199113, 362584510633666621, 7580578211464070863, 166099466140519353035, 3806162403831340850651

Offset: 0

Vladimir Baltic, Vladeta Jovovic, Jan 05 2003

nonn

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

Cf. A000255, A055790, A001883, A001887, A075851, A075852.

a:= proc(n) option remember; `if`(n<4, 1,
      (n-1)*a(n-1) +(n-3)*a(n-2) +a(n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 10 2014

a = DifferenceRoot[Function[{y, n}, {-y[n] - n y[n+1] - (n+2) y[n+2] + y[n+3] == 0, y[0] == 1, y[1] == 1, y[2] == 1, y[3] == 1}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

From Vladeta Jovovic, Jul 16 2007: (Start)
G.f.: x/(1+x)*Sum_{n>=0} (n+1)!*(x/(1+x)^2)^n.
a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*binomial(n+k-2,2*k-2). (End)
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Aug 25 2014

More terms from Alois P. Heinz, Jan 10 2014

A306543 Number T(n,k) of permutations p of [n] such that |p(j)-j| >= k (for all j in [n]); triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

Original entry on oeis.org

1, 1, 2, 1, 6, 2, 24, 9, 1, 120, 44, 4, 720, 265, 29, 1, 5040, 1854, 206, 8, 40320, 14833, 1708, 112, 1, 362880, 133496, 15702, 1168, 16, 3628800, 1334961, 159737, 13365, 436, 1, 39916800, 14684570, 1780696, 159414, 6984, 32, 479001600, 176214841, 21599745, 2036488, 114124, 1708, 1

Offset: 0

Alois P. Heinz, Feb 22 2019

			Triangle T(n,k) begins:
          1;
          1;
          2,         1;
          6,         2;
         24,         9,        1;
        120,        44,        4;
        720,       265,       29,       1;
       5040,      1854,      206,       8;
      40320,     14833,     1708,     112,      1;
     362880,    133496,    15702,    1168,     16;
    3628800,   1334961,   159737,   13365,    436,    1;
   39916800,  14684570,  1780696,  159414,   6984,   32;
  479001600, 176214841, 21599745, 2036488, 114124, 1708, 1;
  ...

Alois P. Heinz, Rows n = 0..22, flattened
Wikipedia, Permutation

Columns k=0-6 give (offsets may differ): A000142, A000166, A001883, A075851, A075852, A183242, A183243.
T(2n,n) gives A000012.
T(2n+1,n) gives A000079.
T(2n+2,n) gives A183245 for n > 0.
T(2n+3,n) gives A183246 for n > 0.
T(2n+4,n) gives A183247 for n > 0.
Cf. A183244, A299789.

T:= proc(n, k) option remember; `if`(n=0, 1, LinearAlgebra[
      Permanent](Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))
    end:
seq(seq(T(n, k), k=0..floor(n/2)), n=0..12);

T[n_, k_] := T[n, k] = If[n==0, 1, Permanent[Table[
     If[Abs[i-j] >= k, 1, 0], {i, n}, {j, n}]]];
Table[Table[T[n, k], {k, 0, Floor[n/2]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 26 2021, after Alois P. Heinz *)

T(n,k) = Sum_{j=k..floor(n/2)} A299789(n,j) for n > 0.

A001885 Hit polynomials.

Original entry on oeis.org

2, 2, 10, 28, 207, 1288, 10366, 91296, 903037, 9832848, 117032570, 1510932116, 21028774738, 313832463386, 4999133311044, 84655108256252, 1518546437350265, 28763765236019284, 573689119174695326, 12017485839703597024, 263787711208968183879, 6054632852404055079936

Offset: 2

N. J. A. Sloane

nonn

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).

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

Third column of A080018.

Cf. A001883-A001891.

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

a(21)-a(23) from Vaclav Kotesovec, Oct 10 2017

A001886 Hit polynomials.

Original entry on oeis.org

3, 6, 44, 180, 1407, 10384, 92896, 911512, 9913152, 117788056, 1519021046, 21123287848, 315034832581, 5015656588706, 84899016219708, 1522394744470356, 28828385427350245, 574839634258405032, 12039133083940334978, 264216869431056251276, 6063573884814663905952

Offset: 3

N. J. A. Sloane

nonn

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).

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

Fourth column of A080018.

Cf. A001883-A001891.

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

a(21)-a(23) from Vaclav Kotesovec, Oct 10 2017

A001888 Hit polynomials.

Original entry on oeis.org

1, 1, 1, 4, 21, 122, 849, 6719, 59873, 593686, 6483027, 77309508, 999569969, 13927664613, 208044077633, 3316415176712, 56193522437465, 1008499234742158, 19110533105114433, 381290148293261075, 7989548583615385153, 175418232627066361514, 4027213499971769192903, 96489861550805864197512

Offset: 1

N. J. A. Sloane

nonn

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).

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

Second column of A080061.

Cf. A001883-A001891.

More terms from Vladeta Jovovic, Vladimir Baltic, Jan 23 2003

a(21)-a(24) from Vaclav Kotesovec, Oct 10 2017

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A292574 Number of permutations p of {1,2,...,n} such that p(i)-i not in {-1,0,1,2}.

Views

Author

Keywords

Links

Crossrefs

A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001884 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001890 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A078509 Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A306543 Number T(n,k) of permutations p of [n] such that |p(j)-j| >= k (for all j in [n]); triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001885 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001886 Hit polynomials.

Views