OFFSET
0,5
COMMENTS
Permanent of the binary matrix with an entry equal to 0 iff the entry is on the main diagonal or the main antidiagonal. - Simone Severini, Oct 14 2004
Comment from Toby Gottfried, Dec 05 2008: (Start)
Suppose you have a group of married couples (plus perhaps one other person).
You wish to organize a gift exchange so that:
- each person gives and receives one gift.
- no one gives himself a gift.
- no one gives his/her spouse a gift.
Then the sequence gives the number of ways that this can be done. (End)
REFERENCES
S. Hertzsprung, Losning og Udvidelse af Opgave 402, Tidsskrift for Math., 4 (1879), 134-140.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 187.
Simpson, Todd; Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Robert Israel, Table of n, a(n) for n = 0..200
S. Even and J. Gillis, Derangements and Laguerre polynomials, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 1, January 1976, pp. 135-143.
Mathematics Stack Exchange, Derivation of integral formula for even n and for odd n.
T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 1906-1923. [Annotated scans of selected pages]. See Vol. 3 page 468. There may have been some confusion here of this sequence with A002777.
John Riordan and N. J. A. Sloane, Correspondence, 1974
T. Simpson, Letter to N. J. A. Sloane, Mar. 1992
T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
FORMULA
a(n) = (n-1)*a(n-1) + 2*(n-d)*a(n-e), where (d, e) = (2, 4) if n even, (1, 2) if n odd.
a(n) = Integral_{ x = 0..infinity } (x^2-4*x+2)^k * (x-1)^m * exp(-x) dx, where n=2*k+m, m=n mod 2. - Felix A. Pahl, Dec 27 2011
Recurrence: (n-3)*(3*n^3 - 36*n^2 + 137*n - 162)*a(n) = (n-5)*(3*n^3 - 27*n^2 + 71*n - 50)*a(n-1) + (n-2)*(3*n^5 - 45*n^4 + 248*n^3 - 606*n^2 + 608*n - 156)*a(n-2) - 2*(n-3)*(3*n^3 - 28*n^2 + 87*n - 94)*a(n-3) + 2*(3*n^5 - 51*n^4 + 334*n^3 - 1060*n^2 + 1650*n - 1028)*a(n-4) - 4*(n-4)*(n^2 + n - 14)*a(n-5) - 4*(n-5)*(n-4)*(n-2)*(3*n^3 - 27*n^2 + 74*n - 58)*a(n-6). - Vaclav Kotesovec, Mar 07 2014
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Mar 07 2014
EXAMPLE
G.f. = 1 + 4*x^4 + 16*x^5 + 80*x^6 + 672*x^7 + 4752*x^8 + ... - Michael Somos, Jun 17 2023
MAPLE
a:= proc(n) option remember; `if`(n<5, [1, 0$3, 4][n+1],
(n-1)*a(n-1)+2*`if`(n::even, (n-2)*a(n-4), (n-1)*a(n-2)))
end:
seq(a(n), n=0..23); # Alois P. Heinz, Jun 27 2020
MATHEMATICA
a[n_] := Integrate[m = Mod[n, 2]; k = (n-m)/2; (x^2-4*x+2)^k*(x-1)^m*Exp[-x], {x, 0, Infinity}]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Sep 09 2013, after Felix A. Pahl *)
nmax=20; b=ConstantArray[0, nmax+1]; b[[1]]=1; b[[2]]=0; b[[3]]=0; b[[4]]=0; b[[5]]=4; Do[b[[n+1]] = (n-1)*b[[n]] + If[EvenQ[n], 2*(n-2)*b[[n-3]], 2*(n-1)*b[[n-1]]], {n, 5, nmax}]; b (* Vaclav Kotesovec, Mar 07 2014 *)
a[ n_] = If[n<4, Boole[n==0], With[{m =2-Mod[n, 2]}, a[n-1]*(n-1) + 2*(n-m)*a[n-2*m]]]; (* Michael Somos, Jun 17 2023 *)
PROG
(PARI) {a(n) = if(n<4, n==0, my(m = 2-n%2); a(n-1)*(n-1) + 2*(n-m)*a(n-2*m))}; /* Michael Somos, Jun 17 2023 */
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Sep 24 2001
STATUS
approved