|
|
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
|
|
|
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
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}):
|
|
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 Herman Jamke (hermanjamke(AT)fastmail.fm), May 16 2007
|
|
STATUS
|
approved
|
|
|
|