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,5

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

Alois P. Heinz, Table of n, a(n) for n = 0..50

Mathieu Guay-Paquey and T. Kyle Petersen, The generating function for total displacement, arXiv:1404.4674 [math.CO], 2014.

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

Prog

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

Crossrefs

Cf. A072948, A062869.

Sequence in context: A045915 A052609 A077613 * A104531 A225050 A045738

Adjacent sequences: A072946 A072947 A072948 * A072950 A072951 A072952

Keyword

nonn

Author

Benoit Cloitre, Aug 20 2002

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

Status

approved