A080018 -id:A080018 - cp's OEIS frontend

A001883 Number of permutations s of {1,2,...,n} such that |s(i)-i|>1 for each i=1,2,...,n.

1, 0, 0, 0, 1, 4, 29, 206, 1708, 15702, 159737, 1780696, 21599745, 283294740, 3995630216, 60312696452, 970234088153, 16571597074140, 299518677455165, 5711583170669554, 114601867572247060, 2413623459384988298, 53238503492701261201, 1227382998752177970288, 29520591675204638641249

Offset: 0

N. J. A. Sloane

nonn

Permanent of the (0,1)-matrix having (i,j)-th entry equal to 0 iff this is on the first lower-diagonal, diagonal or the first upper-diagonal. - Simone Severini, Oct 14 2004

J. Riordan, "The enumeration of permutations with three-ply staircase restrictions," unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963.
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).

Eric M. Schmidt, Table of n, a(n) for n = 0..200
Dmitry Efimov, Determinants of generalized binary band matrices, arXiv:1702.05655 [math.RA], 2017.
J. Riordan, Letter, Oct 31 1977
N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper
Donovan Young, The Number of Domino Matchings in the Game of Memory, J. Int. Seq., Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 X k Game of Memory, J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Cf. A001884-A001891, A075851, A075852.
Also a diagonal of A080018.
Column k=0 of A323671.

b:= proc(n, s) option remember; `if`(n=0, 1, add(
      `if`(abs(n-i)<=1, 0, b(n-1, s minus {i})), i=s))
    end:
a:= n-> b(n, {$1..n}):
seq(a(n), n=0..15);  # Alois P. Heinz, Jul 04 2015

b[n_, s_List] := b[n, s] = If[n == 0, 1, Sum[If[Abs[n-i] <= 1, 0, b[n-1, s ~Complement~ {i}]], {i, s}]]; a[n_] := b[n, Range[n]]; Table[Print[a[n]]; a[n], {n, 4, 24}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)

permRWNb(a)=n=matsize(a)[1]; if(n==1,return(a[1,1])); sg=1; in=vectorv(n); x=in; x=a[,n]-sum(j=1,n,a[,j])/2; p=prod(i=1,n,x[i]); for(k=1,2^(n-1)-1,sg=-sg; j=valuation(k,2)+1; z=1-2*in[j]; in[j]+=z; x+=z*a[,j]; p+=prod(i=1,n,x[i],sg)); return(2*(2*(n%2)-1)*p)
for(n=1,23,a=matrix(n,n,i,j,abs(i-j)>1);print1(permRWNb(a)",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 16 2007

a(n) = (n+1)*a(n-1) - (n-3)*a(n-2) - (n-4)*a(n-3) + (n-4)*a(n-4) + a(n-5) + (-1)^n * Lucas(n-3), n > 4. [Riordan] (Note: There is a slight mistake in Riordan's paper. On p. 3 it should say that a_5 = 3.) - Eric M. Schmidt, Oct 09 2017
From Vaclav Kotesovec, Oct 10 2017: (Start)
a(n) = n*a(n-1) + 4*a(n-2) - 3*(n-3)*a(n-3) + (n-4)*a(n-4) + 2*(n-5)*a(n-5) - (n-7)*a(n-6) - a(n-7).
a(n) ~ exp(-3) * n!.
(End)

More terms and better description from Reiner Martin, Oct 14 2002
More terms from Vladimir Baltic, Vladeta Jovovic, Jan 04 2003
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 16 2007
a(22)-a(24) from Alois P. Heinz, Jul 04 2015
a(0)-a(3) from Eric M. Schmidt, Oct 09 2017

A058057 Triangle giving coefficients of ménage hit polynomials.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 1, 1, 1, 6, 6, 8, 3, 1, 10, 20, 38, 35, 16, 1, 15, 50, 134, 213, 211, 96, 1, 21, 105, 385, 915, 1479, 1459, 675, 1, 28, 196, 952, 3130, 7324, 11692, 11584, 5413, 1, 36, 336, 2100, 9090, 28764, 65784, 104364, 103605, 48800

Offset: 0

N. J. A. Sloane, Dec 02 2000

Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if 0<=i-j<=1 else m(i,j)=1. - Vladeta Jovovic, Jan 23 2003

			1; 1,0; 1,1,0; 1,3,1,1; 1,6,6,8,3; ...

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.

T. D. Noe, Rows n = 0..100 of triangle, flattened

Diagonals give A000271, A000426, A000222, A000386, A000450, A058085, A058086.

Cf. A080018, A080061.

V := proc(n) local k; add( binomial(2*n-k,k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r,s) coeff( V(r),x,s ); end; a := (n,k)->W(n,n-k);

max = 9; f[x_, y_] := Sum[n!*((x*y)^n/(1 + x*(y-1))^(2*n+1)), {n, 0, max}]; Flatten[ MapIndexed[ Take[#1, #2[[1]]] & , CoefficientList[ Series[f[x, y], {x, 0, max}, {y, 0, max}], {x, y}]]] (*Jean-François Alcover, Jun 29 2012, after Vladeta Jovovic *)

G.f.: Sum(n!*(x*y)^n/(1+x*(y-1))^(2*n+1),n=0..infinity). [Vladeta Jovovic, Dec 13 2009]

A080061 Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if 0<=i-j<=2 else m(i,j)=1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 1, 4, 8, 10, 1, 5, 21, 38, 34, 21, 1, 33, 122, 209, 206, 109, 40, 1, 236, 849, 1400, 1351, 836, 295, 72, 1, 1918, 6719, 10849, 10543, 6629, 2821, 715, 125, 1, 17440, 59873, 95516, 92708, 60284, 26870, 8372, 1604, 212, 1, 175649, 593686

Offset: 0

Vladeta Jovovic, Vladimir Baltic, Jan 23 2003

			1;
0,1;
0,1,1;
0,1,4,1;
1,4,8,10,1;
5,21,38,34,21,1;
... P(5; x) = Permanent(Matrix(5, 5, [[x,1,1,1,1],[x,x,1,1,1],[x,x,x,1,1],[1,x,x,x,1],[1,1,x,x,x]]))= 5+21*x+38*x^2+34*x^3+21*x^4+x^5.

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. See Table 1. - N. J. A. Sloane, Aug 27 2013 (See A001883)

R. J. Mathar, Table of n, a(n) for n = 0..209

Row sums = A000142, first column = A001887, second column = A001888, third column = A001889, fourth column = A001890, A080018.

Cf. A001883.

A080061_line := proc(n)
    local M,r,c,p,pord ;
    if n = 0 then
        return [1] ;
    else
        M := Matrix(n,n) ;
        for r to n do
        for c to n do
            if r-c >=0 and r-c <=2 then
                M[r,c] := x ;
            else
                M[r,c] := 1 ;
            end if;
        end do:
        end do:
        p := LinearAlgebra[Permanent](M) ;
        pord := degree(p) ;
        [seq( coeff(p,x,r),r=0..pord)] ;
    end if;
end proc:
for n from 0 to 10 do
    print(A080061_line(n)) ;
end do: # R. J. Mathar, Sep 18 2013

M[n_] := Table[If[0 <= i-j <= 2, x, 1], {i, 1, n}, {j, 1, n}]; M[0]={{1}}; Table[CoefficientList[Permanent[M[n]], x], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 06 2016 *)

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

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

cp's OEIS Frontend

A001883 Number of permutations s of {1,2,...,n} such that |s(i)-i|>1 for each i=1,2,...,n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A058057 Triangle giving coefficients of ménage hit polynomials.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A080061 Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if 0<=i-j<=2 else m(i,j)=1.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A001884 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001885 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001886 Hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Extensions