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

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

References

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

Links

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

Crossrefs

Cf. A001884-A001891, A075851, A075852.

Also a diagonal of A080018.

Column k=0 of A323671.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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)

Extensions

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