login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056151 Distribution of maximum inversion table entry. 5
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 (list; table; graph; refs; listen; history; text; internal format)
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: A192020 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 02:05 EDT 2022. Contains 356986 sequences. (Running on oeis4.)