login
Distribution of maximum inversion table entry.
5

%I #40 Aug 15 2024 03:33:24

%S 1,1,1,1,3,2,1,7,10,6,1,15,38,42,24,1,31,130,222,216,120,1,63,422,

%T 1050,1464,1320,720,1,127,1330,4686,8856,10920,9360,5040,1,255,4118,

%U 20202,50424,80520,91440,75600,40320,1,511,12610,85182,276696,558120,795600,851760,685440,362880

%N Distribution of maximum inversion table entry.

%C T(n,k) is the number of permutations p of [n] such that max(p(i) - i) = k. Example: T(3,0) = 1 because for p = 123 we have max(p(i) - i) = 0; T(3,1) = 3 because for p = 132, 213, 231 we have max(p(i) - i) = 1; T(3,2) = 2 because for p = 312, 321 we have max(p(i) - i) = 2. - _Emeric Deutsch_, Nov 12 2004

%C T(n,k) is the number of permutations of [n] for which the first subcedance occurs at position n + 2 - k. A subcedance of pi occurs at position i if i>pi(i). For example, with n = 3 and k = 2, T(n,k) = 3 counts 132, 231, 321 in each of which the first subcedance occurs at position n+2-k = 3. - _David Callan_, Dec 14 2021

%D R. Sedgewick and Ph. Flajolet, "An Introduction to the Analysis of Algorithms", Addison-Wesley, 1996, ISBN 0-201-40009-X, table 6.10 (page 356)

%H Alois P. Heinz, <a href="/A056151/b056151.txt">Rows n = 1..141, flattened</a>

%H Mathilde Bouvel, Lapo Cioni, and Luca Ferrari, <a href="https://arxiv.org/abs/2204.12936">Preimages under the bubblesort operator</a>, arXiv:2204.12936 [math.CO], 2022. See Table 1 p. 12.

%H E. Deutsch, I. M. Gessel and D. Callan, <a href="http://www.jstor.org/stable/2589362">Problem 10634: Permutation Parameters with the Same Distribution</a>, Amer. Math. Monthly, 107 (2000), 567-568.

%F Table[ -((-1 + k)^(1 - k + n)*(-1 + k)!) + k^(-k + n)*k!, {n, 1, 9}, {k, 1, n} ]

%F T(n, k) = k!(k+1)^(n-k) - (k-1)!k^(n-k+1) if 0<k<=n; T(n, 0)=1. - _Emeric Deutsch_, Nov 12 2004

%F From _Peter Luschny_, Dec 14 2021: (Start)

%F We assume T with offset 0.

%F T(n, k) = k!^2 * (n-k)! * [y^k] [x^(n-k)] (exp(exp(x)*y + x)*(exp(x)*y - y + 1)).

%F T(n, k) = k!*A343237(n, k). (End)

%e Triangle starts:

%e 1;

%e 1, 1;

%e 1, 3, 2;

%e 1, 7, 10, 6;

%e 1, 15, 38, 42, 24;

%e 1, 31, 130, 222, 216, 120;

%e 1, 63, 422, 1050, 1464, 1320, 720;

%e 1, 127, 1330, 4686, 8856, 10920, 9360, 5040;

%e 1, 255, 4118, 20202, 50424, 80520, 91440, 75600, 40320;

%p T:=proc(n,k) if k>0 and k<=n then k!*(k+1)^(n-k)-(k-1)!*k^(n-k+1) elif k=0 then 1 else 0 fi end: TT:=(n,k)->T(n,k-1): matrix(10,10,TT);

%p # Alternative, assuming offset 0:

%p egf := exp(exp(x)*y + x)*(exp(x)*y - y + 1): ser := series(egf, x, 12):

%p cx := n -> series(coeff(ser, x, n), y, 12):

%p T := (n, k) -> k!^2 * (n-k)! * coeff(cx(n - k), y, k):

%p for n from 0 to 6 do seq(T(n, k), k=0..n) od; # _Peter Luschny_, Dec 14 2021

%t T[_, 0] = 1; T[n_, k_] := k! (k + 1)^(n - k) - (k - 1)! k^(n - k + 1);

%t Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* _Jean-François Alcover_, May 03 2017 *)

%Y Columns and diagonals give A000225, A018927, A056182, A000142, A056197.

%Y Cf. A343237.

%K nonn,tabl,easy

%O 1,5

%A _Wouter Meeussen_, Aug 05 2000

%E More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000