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

Author

Wouter Meeussen, Aug 05 2000

Keywords

• nonn
• tabl
• easy

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

Examples

			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;
		

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.

Crossrefs

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

Cf. A343237.

Programs

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 *)

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 0Emeric 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)

Extensions

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