A072948 -id:A072948 - cp's OEIS frontend

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

1, 1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 4, 1, 4, 12, 24, 35, 24, 20, 1, 5, 18, 46, 93, 137, 148, 136, 100, 36, 1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252, 1, 7, 33, 115, 327, 765, 1523, 2553, 3696, 4852, 5708, 5892, 5452, 4212, 2844, 1764, 576, 1, 8, 42, 164, 524

Offset: 0

Olivier Gérard, Jun 26 2001

Number of possible values is 1,2,3,5,7,10,13,17,21,... = A033638. Maximum distance divided by 2 is the same minus one, i.e., 0,1,2,4,6,9,12,16,20,... = A002620.

T. Kyle Petersen and Bridget Eileen Tenner proved that T(n,k) is also the number of permutations of n for which the sum of descent differences equals k. - Susanne Wienand, Sep 11 2014

			Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7,  9,   4;
  1, 4, 12, 24,  35,  24,  20;
  1, 5, 18, 46,  93, 137, 148, 136, 100,  36;
  1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252;
  ...
(4,3,1,2) has distances (3,1,2,2), sum is 8 and there are 3 other permutations of degree 4 with this sum.

D. E. Knuth, The Art of Computer Programming, vol. 3, (1998), page 22 (exercise 28) and page 597 (solution and comments).

Daniel Graf and Alois P. Heinz, Rows n = 0..50, flattened (first 31 rows from Alois P. Heinz)
Max Alekseyev, Proof that T(n,k) is even for k>=n, SeqFan Mailing List, Dec 07 2006
Andreas Bärtschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna, and Thomas Tschager, On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016. See pp. 1, 3-5, 13. - _Daniel Graf_, Jun 20 2016
P. Diaconis and R. L. Graham, Spearman's Footrule as a Measure of Disarray, J. Royal Stat. Soc. B, 39 (1977), 262-268.
FindStat - Combinatorial Statistic Finder, The depth of a permutation., The sum of the descent differences of a permutations.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, arXiv:1404.4674 [math.CO], 2014.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, The Electronic Journal of Combinatorics, 21(3) (2014), #P3.37.
Dirk Liebhold, Gabriele Nebe, and Angeles Vazquez-Castro, Network coding and spherical buildings, arXiv preprint arXiv:1612.07177 [cs.IT], 2016. See p. 4.
T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012.
Balázs R. Sziklai, Attila Gere, Károly Héberger, and Jochen Staudacher, rSRD: An R package for the Sum of Ranking Differences statistical procedure, arXiv:2502.03208 [math.ST], 2025. See p. 34.

Cf. A005990, A009006, A062866, A062867, A062870, A072949, A301897.
Row sums give A000142.
T(2n,n) gives A072948.
A357329 is a sub-triangle.

# The following program yields the entries of the specified row n
n := 9: with(combinat): P := permute(n): excsum := proc (p) (1/2)*add(abs(p[i]-i), i = 1 .. nops(p)) end proc: f[n] := sort(add(t^excsum(P[j]), j = 1 .. factorial(n))): seq(coeff(f[n], t, j), j = 0 .. floor((1/4)*n^2)); # Emeric Deutsch, Apr 02 2010
# Maple program using the g.f. given by Guay-Paquey and Petersen:
g:= proc(h, n) local i, j; j:= irem(h, 2, 'i');
       1-`if`(h=n, 0, (i+1)*z*t^(i+j)/g(h+1, n))
    end:
T:= n-> (p-> seq(coeff(p, t, k), k=0..degree(p)))
        (coeff(series(1/g(0, n), z, n+1), z, n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 02 2014

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]]]; T[n_] := Function[p, Table[ Coefficient[p, t, k], {k, 0, Exponent[p, t]}]][SeriesCoefficient[ 1/g[0, n], {z, 0, n}]]; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 07 2016, after Alois P. Heinz *)
f[i_] := If[i == 1, 1, -(i-1)^2 t^(2i - 3) z^2];
g[i_] := 1 - (2i - 1) t^(i-1) z;
cf = ContinuedFractionK[f[i], g[i], {i, 1, 5}];
CoefficientList[#, t]& /@ CoefficientList[cf + O[z]^10, z] // Rest // Flatten (* Jean-François Alcover, Nov 25 2018, after Mathieu Guay-Paquet *)

# The following Sage program
# yields the entries of the first n rows
# as a list of lists
def get_first_rows(n):
    R, t = PolynomialRing(ZZ, 't').objgen()
    S, z = PowerSeriesRing(R, 'z').objgen()
    gf = S(1).add_bigoh(1)
    for i in srange(n, 0, -1):
        a = (i+1) // 2
        b = i // 2
        gf = 1 / (1 - a * t^b * z * gf)
    return [list(row) for row in gf.shift(-1)]
# Mathieu Guay-Paquet, Apr 30 2014

From Mathieu Guay-Paquet, Apr 30 2014: (Start)
G.f.: 1/(1-z/(1-t*z/(1-2*t*z/(1-2*t^2*z/(1-3*t^2*z/(1-3*t^3*z/(1-4*t^3*z/(1-4*t^4*z/(...
This is a continued fraction where the (2i)th numerator is (i+1)*t^i*z, and the (2i+1)st numerator is (i+1)*t^(i+1)*z for i >= 0. The coefficient of z^n gives row n, n >= 1, and the coefficient of t^k gives column k, k >= 0. (End)
From Alois P. Heinz, Oct 02 2022: (Start)
Sum_{k=0..floor(n^2/4)} k * T(n,k) = A005990(n).
Sum_{k=0..floor(n^2/4)} (-1)^k * T(n,k) = A009006(n). (End).

T(0,0)=1 prepended by Alois P. Heinz, Oct 03 2022

A357329 Triangular array read by rows: T(n, k) = number of occurrences of 2k as a sum |1 - p(1)| + |2 - p(2)| + ... + |n - p(n)|, where (p(1), p(2), ..., p(n)) ranges through the permutations of (1,2,...,n), for n >= 1, 0 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 1, 4, 12, 24, 35, 1, 5, 18, 46, 93, 137, 1, 6, 25, 76, 187, 366, 591, 1, 7, 33, 115, 327, 765, 1523, 2553, 1, 8, 42, 164, 524, 1400, 3226, 6436, 11323, 1, 9, 52, 224, 790, 2350, 6072, 13768, 27821, 50461, 1, 10, 63, 296, 1138, 3708, 10538, 26480, 59673, 121626, 226787

Offset: 1

Clark Kimberling, Sep 24 2022

In the Name, (1,2,...,n) can be replaced by any of its permutations. The first 10 row sums are the first 10 terms of A263898.

			First 8 rows:
  1
  1     1
  1     2     3
  1     3     7     9
  1     4    12    24     35
  1     5    18    46     93     137
  1     6    25    76    187     366    591
  1     7    33   115    327     765   1523    2553
For n=3, write
  123   123   123   123   123   123
  123   132   213   231   312   312
  000   011   110   112   211   211,
where row 3 represents |1 - p(1)| + |2 - p(2)| + |3 - p(n)| for the 6 permutations (p(1), p(2), p(2)) in row 3. The sums in row 3 are 0,2,2,4,4,4, so that the numbers 0, 2, 4 occur with multiplicities 1, 2, 3, as in row 3 of the array.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000142, A263898.
Subtriangle of A062869.
T(2n,n) gives A072948 (for n>0).

g:= proc(h, n) local i, j; j:= irem(h, 2, 'i');
       1-`if`(h=n, 0, (i+1)*z*t^(i+j)/g(h+1, n))
    end:
T:= n-> (p-> seq(coeff(p, t, k), k=0..n-1))
        (coeff(series(1/g(0, n), z, n+1), z, n)):
seq(T(n), n=1..12);  # Alois P. Heinz, Oct 02 2022

p[n_] := p[n] = Permutations[Range[n]];
f[n_, k_] := f[n, k] = Abs[p[n][[k]] - Range[n]]
c[n_, k_] := c[n, k] = Total[f[n, k]]
t[n_] := Table[c[n, k], {k, 1, n!}]
u = Table[Count[t[n], 2 m], {n, 1, 10}, {m, 0, n - 1}]  (* A357329, array *)
Flatten[u]  (* A357329, sequence *)

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

Original entry on oeis.org

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

Benoit Cloitre, Aug 20 2002

nonn

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)

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.

Cf. A072948, A062869.

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

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

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

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

cp's OEIS Frontend

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A357329 Triangular array read by rows: T(n, k) = number of occurrences of 2k as a sum |1 - p(1)| + |2 - p(2)| + ... + |n - p(n)|, where (p(1), p(2), ..., p(n)) ranges through the permutations of (1,2,...,n), for n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions