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

0, 1, 0, 0, 8, 20, 96, 656, 5568, 48912, 494080, 5383552, 65097600, 840566080, 11833898496, 176621049600, 2838024476672, 48060623405312, 868000333234176, 16441638519762944, 329723762151352320, 6907027877807330304

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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.

Number of magic permutation matrices of order n. - Chai Wah Wu, Jan 15 2019

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

References

• 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

• Jean-François Alcover, Table of n, a(n) for n = 0..100
• F. Rakotondrajao, Magic squares, rook polynomials and permutations, Séminaire Lotharingien de Combinatoire, vol. 54A, article B54Ac, 2006.
• T. Simpson, Letter to N. J. A. Sloane, Mar. 1992
• T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
• E. Vatutin, Upper bound for the number of diagonal transversals in a Latin square (in Russian).

Crossrefs

Cf. A003471, A064280.

Programs

Mathematica

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}];
a[n_ /; EvenQ[n]] := With[{m = n/2}, m*(x[2*m] - (2*m - 3)*x[2*m - 1])];
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]];
Table[a[n], {n, 0, 21}] // Quiet (* Jean-François Alcover, Jun 29 2018 *)

PARI

a(n) = {my(v = vector(n)); \\ v is A003471
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])));
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

Formula

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

Conjecture D-finite with recurrence (365968635435167109808*n^2 -5566069866485493251505*n +20525522573033552369132)*a(n) +(-1215369044326430542311*n^2 +19103429957352794982854*n -73690801030090785944295)*a(n-1) +(-365968635435167109808*n^4 +6663975772790994580929*n^3 -35836353442786038818589*n^2 +34878550744402035813586*n +124043542472821007763204)*a(n-2) +(483431773456096322695*n^4 -10754417727097457203127*n^3 +85154149458907095778621*n^2 -277683967994722584206067*n +286254870342835757751852)*a(n-3) +2*(-393241909113483884738*n^4 +9142334951839265043383*n^3 -78427160779754271402777*n^2 +309283968160862567580813*n -465057422344277141977923)*a(n-4) +2*(-745044547502580209919*n^4 +21471238686323774026196*n^3 -222067832543690193789255*n^2 +944698954932049830084232*n -1372732531859619119793978)*a(n-5) +4*(365968635435167109808*n^4 -5227374504728642916627*n^3 +19793104565012302929789*n^2 +391834816007939927082*n -57365695502678698166146)*a(n-6) +4*(-483431773456096322695*n^4 +7592214312314395379733*n^3 -45284933032689911393913*n^2 +117535885088909103449165*n -84799883220517633629252)*a(n-7) +8*(n-7)*(393241909113483884738*n^3 -4789400677912625536335*n^2 +17834478528905815208536*n -23668675533486426523455)*a(n-8) +8*(n-7)*(n-8)*(745044547502580209919*n^2 -6086915962816073505121*n +12854159797389104313178)*a(n-9)=0. - R. J. Mathar, Feb 27 2025