|
%I M3525 #76 Jun 19 2023 07:07:19
%S 1,0,0,0,4,16,80,672,4752,48768,440192,5377280,59245120,839996160,
%T 10930514688,176547098112,2649865335040,48047352500224,
%U 817154768973824,16438490531536896,312426715251262464,6906073926286725120,145060238642780180480,3495192502897779875840
%N Number of permutations with no hits on 2 main diagonals.
%C 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
%C Comment from _Toby Gottfried_, Dec 05 2008: (Start)
%C Suppose you have a group of married couples (plus perhaps one other person).
%C You wish to organize a gift exchange so that:
%C - each person gives and receives one gift.
%C - no one gives himself a gift.
%C - no one gives his/her spouse a gift.
%C Then the sequence gives the number of ways that this can be done. (End)
%D S. Hertzsprung, Losning og Udvidelse af Opgave 402, Tidsskrift for Math., 4 (1879), 134-140.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 187.
%D Simpson, Todd; Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Robert Israel, <a href="/A003471/b003471.txt">Table of n, a(n) for n = 0..200</a>
%H S. Even and J. Gillis, <a href="https://doi.org/10.1017/S0305004100052154">Derangements and Laguerre polynomials</a>, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 1, January 1976, pp. 135-143.
%H Mathematics Stack Exchange, Derivation of integral formula <a href="http://math.stackexchange.com/a/73364/6622">for even n</a> and <a href="http://math.stackexchange.com/a/94443/6622">for odd n</a>.
%H T. Muir, <a href="/A003471/a003471.pdf">The Theory of Determinants in the Historical Order of Development</a>, 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.
%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>
%H T. Simpson, <a href="/A002777/a002777.pdf">Letter to N. J. A. Sloane, Mar. 1992</a>
%H T. Simpson, <a href="/A007016/a007016.pdf">Permutations with unique fixed and reflected points</a>, Preprint. (Annotated scanned copy)
%F 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.
%F 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
%F 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
%F a(n) ~ exp(-2) * n!. - _Vaclav Kotesovec_, Mar 07 2014
%e G.f. = 1 + 4*x^4 + 16*x^5 + 80*x^6 + 672*x^7 + 4752*x^8 + ... - _Michael Somos_, Jun 17 2023
%p a:= proc(n) option remember; `if`(n<5, [1, 0$3, 4][n+1],
%p (n-1)*a(n-1)+2*`if`(n::even, (n-2)*a(n-4), (n-1)*a(n-2)))
%p end:
%p seq(a(n), n=0..23); # _Alois P. Heinz_, Jun 27 2020
%t 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_ *)
%t 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 *)
%t 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 *)
%o (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 */
%Y Cf. A000166, A002777, A225740.
%Y Column k=0 of A335872.
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_
%E More terms from Larry Reeves (larryr(AT)acm.org), Sep 24 2001
| 