login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001883 Number of permutations s of {1,2,...,n} such that |s(i)-i|>1 for each i=1,2,...,n.
(Formerly M3630 N1475)
24
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 (list; graph; refs; listen; history; text; internal format)
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
Dmitry Efimov, Determinants of generalized binary band matrices, arXiv:1702.05655 [math.RA], 2017.
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
Also a diagonal of A080018.
Column k=0 of A323671.
Sequence in context: A143551 A288913 A100022 * A281600 A135429 A079756
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 11:59 EDT 2024. Contains 371254 sequences. (Running on oeis4.)