cp's OEIS Frontend

A056151 Distribution of maximum inversion table entry.

%I A056151 #40 Aug 15 2024 03:33:24
%S A056151 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 A056151 1050,1464,1320,720,1,127,1330,4686,8856,10920,9360,5040,1,255,4118,
%U A056151 20202,50424,80520,91440,75600,40320,1,511,12610,85182,276696,558120,795600,851760,685440,362880
%N A056151 Distribution of maximum inversion table entry.
%C A056151 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 A056151 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 A056151 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 A056151 Alois P. Heinz, <a href="/A056151/b056151.txt">Rows n = 1..141, flattened</a>
%H A056151 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 A056151 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 A056151 Table[ -((-1 + k)^(1 - k + n)*(-1 + k)!) + k^(-k + n)*k!, {n, 1, 9}, {k, 1, n} ]
%F A056151 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 A056151 From _Peter Luschny_, Dec 14 2021: (Start)
%F A056151 We assume T with offset 0.
%F A056151 T(n, k) = k!^2 * (n-k)! * [y^k] [x^(n-k)] (exp(exp(x)*y + x)*(exp(x)*y - y + 1)).
%F A056151 T(n, k) = k!*A343237(n, k). (End)
%e A056151 Triangle starts:
%e A056151   1;
%e A056151   1,   1;
%e A056151   1,   3,    2;
%e A056151   1,   7,   10,     6;
%e A056151   1,  15,   38,    42,    24;
%e A056151   1,  31,  130,   222,   216,   120;
%e A056151   1,  63,  422,  1050,  1464,  1320,   720;
%e A056151   1, 127, 1330,  4686,  8856, 10920,  9360,  5040;
%e A056151   1, 255, 4118, 20202, 50424, 80520, 91440, 75600, 40320;
%p A056151 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 A056151 # Alternative, assuming offset 0:
%p A056151 egf := exp(exp(x)*y + x)*(exp(x)*y - y + 1): ser := series(egf, x, 12):
%p A056151 cx := n -> series(coeff(ser, x, n), y, 12):
%p A056151 T := (n, k) -> k!^2 * (n-k)! * coeff(cx(n - k), y, k):
%p A056151 for n from 0 to 6 do seq(T(n, k), k=0..n) od; # _Peter Luschny_, Dec 14 2021
%t A056151 T[_, 0] = 1; T[n_, k_] := k! (k + 1)^(n - k) - (k - 1)! k^(n - k + 1);
%t A056151 Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* _Jean-François Alcover_, May 03 2017 *)
%Y A056151 Columns and diagonals give A000225, A018927, A056182, A000142, A056197.
%Y A056151 Cf. A343237.
%K A056151 nonn,tabl,easy
%O A056151 1,5
%A A056151 _Wouter Meeussen_, Aug 05 2000
%E A056151 More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000