A003471 Number of permutations with no hits on 2 main diagonals.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

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)

Examples

			G.f. = 1 + 4*x^4 + 16*x^5 + 80*x^6 + 672*x^7 + 4752*x^8 + ... - _Michael Somos_, Jun 17 2023
		

References

• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 187.
• Todd Simpson, 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.
• S. Hertzsprung, Løsning og Udvidelse af Opgave 402, Tidsskrift for Math., 4 (1879), 134-140.
• 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
• Todd Simpson, Letter to N. J. A. Sloane, Mar. 1992
• Todd Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)

Crossrefs

Cf. A000166, A002777, A225740.

Column k=0 of A335872.

Programs

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 *)

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 */

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..oo} (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

Extensions

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