A072949 Number of permutations p of {1,2,3,...,n} such that Sum_{k=1..n} abs(k-p(k)) = 2n.

1, 0, 0, 0, 4, 24, 148, 744, 3696, 17640, 83420, 390144, 1817652, 8438664, 39117852, 181136304, 838372452, 3879505944, 17952463180, 83086702848, 384626048292, 1781018204328, 8249656925564, 38225193868560, 177179811427796, 821544012667704, 3810648054607212

Offset: 0

Author

Benoit Cloitre, Aug 20 2002

Keywords

• nonn

Comments

a(n) is always even for n>=1. More generally, A062869(n,k) is even whenever k >= n. - Conjectured by Franklin T. Adams-Watters, proved by Max Alekseyev. (see link in A062869)

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..500 (terms 0..50 from Alois P. Heinz)
• Mathieu Guay-Paquey and T. Kyle Petersen, The generating function for total displacement, arXiv:1404.4674 [math.CO], 2014.

Crossrefs

Cf. A072948, A062869.

Programs

Maple

with(linalg): f := (i,j) -> x^(abs(i-j)):for n from 1 to 17 do A := matrix(n,n,f): printf("%d,",coeff(permanent(A),x,2*n)) od: # Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 27 2008

Mathematica

g[h_, n_] := g[h, n] = Module[{i, j}, {i, j} = QuotientRemainder[h, 2]; 1 - If[h==n, 0, (i+1)*z*t^(i+j)/g[h+1, n]]]; a[n_ /; n<4] = 0; a[n_] := SeriesCoefficient[1/g[0, n], {z, 0, n}, {t, 0, n}]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 26}] (* Jean-François Alcover, Jan 07 2016, after Alois P. Heinz *)

PARI

a(n)=sum(k=1,n!,if(sum(i=1,n,abs(i-component(numtoperm(n,k),i)))-2*n,0,1))

Extensions

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 27 2008

a(18)-a(21) from Robert Gerbicz, Nov 21 2010

a(22)-a(26) from Alois P. Heinz, May 02 2014 using formula given by Guay-Paquey and Petersen

a(0)=1 prepended by Alois P. Heinz, Oct 01 2022