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
KEYWORD
AUTHOR
Wouter Meeussen, Aug 05 2000
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000
STATUS
approved