The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). 6
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,6 COMMENTS 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 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 A. Bärtschi, B. Geissmann, D. Graf, T. Hruz, P. Penna, T. Tschager On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016. - 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. M. Guay-Paquet, T. K. Petersen, The generating function for total displacement, The Electronic Journal of Combinatorics, 21(3) (2014), #P3.37. Dirk Liebhold, G Nebe, A Vazquez-Castro, Network coding and spherical buildings, arXiv preprint arXiv:1612.07177 [cs.IT], 2016. T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012. 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). EXAMPLE 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. 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 *) PROG (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 CROSSREFS Cf. A005990, A009006, A062866, A062867, A062870, A072949, A301897. Row sums give A000142. A357329 is a sub-triangle. Sequence in context: A152821 A071943 A357329 * A102473 A011117 A069269 Adjacent sequences: A062866 A062867 A062868 * A062870 A062871 A062872 KEYWORD nonn,tabf,easy,look AUTHOR Olivier Gérard, Jun 26 2001 EXTENSIONS T(0,0)=1 prepended by Alois P. Heinz, Oct 03 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 21 10:18 EDT 2023. Contains 365501 sequences. (Running on oeis4.)