login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056151 Distribution of maximum inversion table entry. 4
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) = 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

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

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

EXAMPLE

{1}, {1, 1}, {1, 3, 2}, {1, 7, 10, 6},

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

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, A056182, A000142, A056197.

Sequence in context: A192020 A171128 A122832 * A134436 A186370 A163626

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 12:21 EST 2017. Contains 294891 sequences.