|
Search: id:A056151
|
|
|
| A056151 |
|
Distribution of maximum inversion table entry. |
|
+0
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
(list; table; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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: A059380 A145035 A122832 this_sequence A134436 A163626 A028246
Adjacent sequences: A056148 A056149 A056150 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
