OFFSET
0,6
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.
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)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
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
STATUS
approved