A056151 Distribution of maximum inversion table entry.

1, 1, 1, 1, 3, 2, 1, 7, 10, 6, 1, 15, 38, 42, 24, 1, 31, 130, 222, 216, 120, 1, 63, 422, 1050, 1464, 1320, 720, 1, 127, 1330, 4686, 8856, 10920, 9360, 5040, 1, 255, 4118, 20202, 50424, 80520, 91440, 75600, 40320, 1, 511, 12610, 85182, 276696, 558120, 795600, 851760, 685440, 362880

Offset

1,5

Comments

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

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

References

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)

Links

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

Mathilde Bouvel, Lapo Cioni, and Luca Ferrari, Preimages under the bubblesort operator, arXiv:2204.12936 [math.CO], 2022. See Table 1 p. 12.

E. Deutsch, I. M. Gessel and D. Callan, Problem 10634: Permutation Parameters with the Same Distribution, Amer. Math. Monthly, 107 (2000), 567-568.

Formula

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

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

From Peter Luschny, Dec 14 2021: (Start)

We assume T with offset 0.

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

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

Example

Triangle starts:
  1;
  1,   1;
  1,   3,    2;
  1,   7,   10,     6;
  1,  15,   38,    42,    24;
  1,  31,  130,   222,   216,   120;
  1,  63,  422,  1050,  1464,  1320,   720;
  1, 127, 1330,  4686,  8856, 10920,  9360,  5040;
  1, 255, 4118, 20202, 50424, 80520, 91440, 75600, 40320;

Maple

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);
# Alternative, assuming offset 0:
egf := exp(exp(x)*y + x)*(exp(x)*y - y + 1): ser := series(egf, x, 12):
cx := n -> series(coeff(ser, x, n), y, 12):
T := (n, k) -> k!^2 * (n-k)! * coeff(cx(n - k), y, k):
for n from 0 to 6 do seq(T(n, k), k=0..n) od; # Peter Luschny, Dec 14 2021

Mathematica

T[_, 0] = 1; T[n_, k_] := k! (k + 1)^(n - k) - (k - 1)! k^(n - k + 1);
Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, May 03 2017 *)

Crossrefs

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

Cf. A343237.

Sequence in context: A367564 A171128 A122832 * A134436 A306226 A186370

Adjacent sequences: A056148 A056149 A056150 * A056152 A056153 A056154

Keyword

nonn,tabl,easy

Author

Wouter Meeussen, Aug 05 2000

Extensions

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

Status

approved