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