login
Number of permutations of length n with 1 fixed and 1 reflected point.
(Formerly M4491)
36

%I M4491 #48 Jan 03 2020 23:30:03

%S 0,1,0,0,8,20,96,656,5568,48912,494080,5383552,65097600,840566080,

%T 11833898496,176621049600,2838024476672,48060623405312,

%U 868000333234176,16441638519762944,329723762151352320,6907027877807330304

%N Number of permutations of length n with 1 fixed and 1 reflected point.

%C Number of distinct solutions to the order n checkerboard problem, including symmetrical solutions: place n pieces on an n X n board so there is exactly one piece in each row, column and main diagonal. Compare A064280.

%C Number of magic permutation matrices of order n. - _Chai Wah Wu_, Jan 15 2019

%C Upper bound for the number of diagonal transversals in a Latin square: A287647(n) <= A287648(n) <= a(n). - _Eduard I. Vatutin_, Jan 02 2020

%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 Jean-François Alcover, <a href="/A007016/b007016.txt">Table of n, a(n) for n = 0..100</a>

%H F. Rakotondrajao, <a href="http://emis.impa.br/EMIS/journals/SLC/wpapers/s54Arakoto.html">Magic squares, rook polynomials and permutations</a>, Séminaire Lotharingien de Combinatoire, vol. 54A, article B54Ac, 2006.

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

%H E. Vatutin, <a href="https://vk.com/wall162891802_1024">Upper bound for the number of diagonal transversals in a Latin square</a> (in Russian).

%F a(2*m) = m*(x(2*m) - (2*m-3)*x(2*m-1)), a(2*m+1) = (2*m+1)*x(2*m) + 3*m*x(2*m-1) - 2*m*(m-1)*x(2*m-2), where x(n) = A003471(n).

%t x[n_] := x[n] = Integrate[If[EvenQ[n], (x^2 - 4*x + 2)^(n/2), (x - 1)*(x^2 - 4*x + 2)^((n - 1)/2)]/E^x, {x, 0, Infinity}];

%t a[n_ /; EvenQ[n]] := With[{m = n/2}, m*(x[2*m] - (2*m - 3)*x[2*m - 1])];

%t a[n_ /; OddQ[n]] := With[{m = (n - 1)/2}, (2*m + 1)*x[2*m] + 3*m*x[2*m - 1] - 2*m*(m - 1)*x[2*m - 2]];

%t Table[a[n], {n, 0, 21}] // Quiet (* _Jean-François Alcover_, Jun 29 2018 *)

%o (PARI)

%o a(n) = {my(v = vector(n)); \\ v is A003471

%o for(n=4, length(v), v[n] = (n-1)*v[n-1] + 2*if(n%2==1, (n-1)*v[n-2], (n-2) * if(n==4,1,v[n-4])));

%o if(n<4, [1,0,0][n], if(n%2==0, n*(v[n] - (n-3)*v[n-1]), 2*n*v[n-1] + 3*(n-1)*v[n-2] - (n-1)*(n-3)*v[n-3])/2)} \\ _Andrew Howroyd_, Sep 12 2017

%Y Cf. A003471, A064280.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_