login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056151 Distribution of maximum inversion table entry. 5

%I

%S 1,1,1,1,3,2,1,7,10,6,1,15,38,42,24,1,31,130,222,216,120,1,63,422,

%T 1050,1464,1320,720,1,127,1330,4686,8856,10920,9360,5040,1,255,4118,

%U 20202,50424,80520,91440,75600,40320,1,511,12610,85182,276696,558120,795600,851760,685440,362880

%N Distribution of maximum inversion table entry.

%C 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

%D 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)

%H Alois P. Heinz, <a href="/A056151/b056151.txt">Rows n = 1..141, flattened</a>

%H E. Deutsch, I. M. Gessel and D.Callan, <a href="http://www.jstor.org/stable/2589362">Problem 10634: Permutation Parameters with the Same Distribution</a>, Amer. Math. Monthly, 107 (2000), 567-568.

%F Table[ -((-1 + k)^(1 - k + n)*(-1 + k)!) + k^(-k + n)*k!, {n, 1, 9}, {k, 1, n} ]

%F 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

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

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

%t T[_, 0] = 1; T[n_, k_] := k! (k + 1)^(n - k) - (k - 1)! k^(n - k + 1);

%t Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* _Jean-Fran├žois Alcover_, May 03 2017 *)

%Y Columns and diagonals give A000225, A018927, A056182, A000142, A056197.

%K nonn,tabl,easy

%O 1,5

%A _Wouter Meeussen_, Aug 05 2000

%E More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 19:47 EDT 2021. Contains 343988 sequences. (Running on oeis4.)