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
Examples
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.
References
- D. E. Knuth, The Art of Computer Programming, vol. 3, (1998), page 22 (exercise 28) and page 597 (solution and comments).
Links
- 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.
Crossrefs
Programs
-
Maple
# 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
-
Mathematica
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 *) -
Sage
# 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
Formula
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).
Extensions
T(0,0)=1 prepended by Alois P. Heinz, Oct 03 2022
Comments