A003471 Number of permutations with no hits on 2 main diagonals. (Formerly M3525)

1, 0, 0, 0, 4, 16, 80, 672, 4752, 48768, 440192, 5377280, 59245120, 839996160, 10930514688, 176547098112, 2649865335040, 48047352500224, 817154768973824, 16438490531536896, 312426715251262464, 6906073926286725120, 145060238642780180480, 3495192502897779875840

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

Cf. A000166, A002777, A225740.

Column k=0 of A335872.

Sequence in context: A316944 A020080 A279361 * A002777 A280923 A118997

Adjacent sequences: A003468 A003469 A003470 * A003472 A003473 A003474

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Sep 24 2001

Status

approved