|
| |
|
|
A056151
|
|
Distribution of maximum inversion table entry.
|
|
3
| |
|
|
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
(list; table; graph; refs; listen; history; 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 (deutsch(AT)duke.poly.edu), Nov 12 2004
|
|
|
REFERENCES
| E. Deutsch and I. M. Gessel, Problem 10634, Amer. Math. Monthly, 107 (2000), 567-568.
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)
|
|
|
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 (deutsch(AT)duke.poly.edu), 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);
|
|
|
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 (wouter.meeussen(AT)pandora.be), Aug 05 2000
|
|
|
EXTENSIONS
| More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000
|
| |
|
|
