login
Number of permutations s of {1,2,...,n} such that |s(i)-i|>1 for each i=1,2,...,n.
(Formerly M3630 N1475)
24

%I M3630 N1475 #102 Oct 30 2022 18:19:58

%S 1,0,0,0,1,4,29,206,1708,15702,159737,1780696,21599745,283294740,

%T 3995630216,60312696452,970234088153,16571597074140,299518677455165,

%U 5711583170669554,114601867572247060,2413623459384988298,53238503492701261201,1227382998752177970288,29520591675204638641249

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

%C 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

%D J. Riordan, "The enumeration of permutations with three-ply staircase restrictions," unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Eric M. Schmidt, <a href="/A001883/b001883.txt">Table of n, a(n) for n = 0..200</a>

%H Dmitry Efimov, <a href="https://arxiv.org/abs/1702.05655">Determinants of generalized binary band matrices</a>, arXiv:1702.05655 [math.RA], 2017.

%H J. Riordan, <a href="/A001861/a001861_1.pdf">Letter, Oct 31 1977</a>

%H N. J. A. Sloane, <a href="/A001883/a001883_21.pdf">Annotated copy of Riordan's Three-Ply Staircase paper</a>

%H Donovan Young, <a href="https://www.emis.de/journals/JIS/VOL21/Young/young2.html">The Number of Domino Matchings in the Game of Memory</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.1.

%H Donovan Young, <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">Generating Functions for Domino Matchings in the 2 X k Game of Memory</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.7.

%H 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 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

%F From _Vaclav Kotesovec_, Oct 10 2017: (Start)

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

%F a(n) ~ exp(-3) * n!.

%F (End)

%p b:= proc(n, s) option remember; `if`(n=0, 1, add(

%p `if`(abs(n-i)<=1, 0, b(n-1, s minus {i})), i=s))

%p end:

%p a:= n-> b(n, {$1..n}):

%p seq(a(n), n=0..15); # _Alois P. Heinz_, Jul 04 2015

%t 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_ *)

%o (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)

%o 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

%Y Cf. A001884-A001891, A075851, A075852.

%Y Also a diagonal of A080018.

%Y Column k=0 of A323671.

%K nonn

%O 0,6

%A _N. J. A. Sloane_

%E More terms and better description from _Reiner Martin_, Oct 14 2002

%E More terms from _Vladimir Baltic_, _Vladeta Jovovic_, Jan 04 2003

%E More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 16 2007

%E a(22)-a(24) from _Alois P. Heinz_, Jul 04 2015

%E a(0)-a(3) from _Eric M. Schmidt_, Oct 09 2017