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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000140 Kendall-Mann numbers: the maximal number of inversions in a permutation on n letters is floor(n(n-1)/4); a(n) is the number of permutations with this many inversions.
(Formerly M1665 N0655)
13

%I M1665 N0655

%S 1,1,2,6,22,101,573,3836,29228,250749,2409581,25598186,296643390,

%T 3727542188,50626553988,738680521142,11501573822788,190418421447330,

%U 3344822488498265,62119523114983224,1214967840930909302

%N Kendall-Mann numbers: the maximal number of inversions in a permutation on n letters is floor(n(n-1)/4); a(n) is the number of permutations with this many inversions.

%C Row maxima of A008302, see example.

%C The term a(0) would be 1: the empty product is one and there is just one coefficient 1=x^0, corresponding to the 1 empty permutation (which has 0 inversions).

%C From Ryen Lapham and _Anant Godbole_, Dec 12 2006: (Start)

%C Also, the number of permutations on {1,2,...,n} for which the number A of monotone increasing subsequences of length 2 and the number D of monotone decreasing 2-subsequences are as close to each other as possible, i.e., 0 or 1. We call such permutations 2-balanced.

%C If 4|n(n-1) then (with A and D as above) the feasible values of A-D are C(n,2), C(n,2)-2,...,2,0,-2,...,-C(n,2), whereas if 4 does not divide n(n-1), A-D may equal C(n,2), C(n,2)-2,...,1,-1,...,-C(n,2). Let a_n(i) equal the number of permutations with A-D the i-th highest feasible value.

%C The sequence in question gives the number of permutations for which A-D=0 or A-D=1, i.e., it equals A_n(j) where j = floor((binomial(n,2)+2)/2). Here is the recursion: a_n(i) = a_n(i-1) + a_{n-1}(i) for 1 <= i <= n and a_n(n+k) = a_n(n+k-1) + a_{n-1}(n+k) - a_n(k) for k >= 1. (End)

%C The only two primes found < 301 are for n = 3 and 6.

%C a(n+1)/a(n) = n - 1/2 + O(1/n^{1-epsilon}) as n --> infinity (compare with A008302, A181609, A001147). - _Mikhail Gaichenkov_, Apr 11 2014

%C Define an ordered list to have n terms with terms t(k) for k=1..n. Specify that t(k) ranges from 1 to k, hence the third term t(3) can be 1, 2, or 3. Find all sums of the terms for all n! allowable arrangements to obtain a maximum sum for the greatest number of arrangements. This number is a(n). For n=4, the maximum sum 7 appears in 6 arrangements: 1114, 1123, 1213, 1222, 1231, and 1132. - _J. M. Bergot_, May 14 2015

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Robert Israel, Robert G. Wilson v and N. J. A. Sloane <a href="/A000140/b000140.txt">Table of n, a(n) for n = 1..400</a> (a(1) to a(61) from Sloane, a(62) to a(350) from Wilson).

%H D. Foata, <a href="http://dx.doi.org/10.1007/978-94-010-1220-1_2">Distributions eulériennes et mahoniennes sur le groupe des permutations</a>, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.

%H M. Gaichenkov, <a href="http://mathoverflow.net/questions/46368/the-property-of-kendall-mann-numbers">The property of Kendall-Mann numbers</a>, MathOverflow, 2010.

%H R. K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>

%H A. Waksman, <a href="http://dx.doi.org/10.1109/T-C.1970.222866">On the complexity of inversions</a>, IEEE Trans. Computers, 19 (1970), 1225-1226.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)">Inversion</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Q-Pochhammer_symbol">q-Pochhammer symbol</a> - _Paul Muljadi_, Jan 18 2011

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F Largest coefficient of (1)(x+1)(x^2+x+1)...(x^(n-1)+...+x+1). - _David W. Wilson_

%F The number of terms is given in A000124.

%F Asymptotics (Mikhail Gaichenkov, 2010): a(n) ~ 6 * n^(n-1) / exp(n). - _Vaclav Kotesovec_, May 17 2015

%e From _Joerg Arndt_, Jan 16 2011: (Start)

%e a(4) = 6 because the among the permutations of 4 elements those with 3 inversions are the most frequent and appear 6 times:

%e [inv. table] [permutation] number of inversions

%e 0: [ 0 0 0 ] [ 0 1 2 3 ] 0

%e 1: [ 1 0 0 ] [ 1 0 2 3 ] 1

%e 2: [ 0 1 0 ] [ 0 2 1 3 ] 1

%e 3: [ 1 1 0 ] [ 2 0 1 3 ] 2

%e 4: [ 0 2 0 ] [ 1 2 0 3 ] 2

%e 5: [ 1 2 0 ] [ 2 1 0 3 ] 3 (*)

%e 6: [ 0 0 1 ] [ 0 1 3 2 ] 1

%e 7: [ 1 0 1 ] [ 1 0 3 2 ] 2

%e 8: [ 0 1 1 ] [ 0 3 1 2 ] 2

%e 9: [ 1 1 1 ] [ 3 0 1 2 ] 3 (*)

%e 10: [ 0 2 1 ] [ 1 3 0 2 ] 3 (*)

%e 11: [ 1 2 1 ] [ 3 1 0 2 ] 4

%e 12: [ 0 0 2 ] [ 0 2 3 1 ] 2

%e 13: [ 1 0 2 ] [ 2 0 3 1 ] 3 (*)

%e 14: [ 0 1 2 ] [ 0 3 2 1 ] 3 (*)

%e 15: [ 1 1 2 ] [ 3 0 2 1 ] 4

%e 16: [ 0 2 2 ] [ 2 3 0 1 ] 4

%e 17: [ 1 2 2 ] [ 3 2 0 1 ] 5

%e 18: [ 0 0 3 ] [ 1 2 3 0 ] 3 (*)

%e 19: [ 1 0 3 ] [ 2 1 3 0 ] 4

%e 20: [ 0 1 3 ] [ 1 3 2 0 ] 4

%e 21: [ 1 1 3 ] [ 3 1 2 0 ] 5

%e 22: [ 0 2 3 ] [ 2 3 1 0 ] 5

%e 23: [ 1 2 3 ] [ 3 2 1 0 ] 6

%e The statistics are reflected by the coefficients of the polynomial

%e (1+x)*(1+x+x^2)*(1+x+x^2+x^3) ==

%e x^6 + 3*x^5 + 5*x^4 + 6*x^3 + 5*x^2 + 3*x^1 + 1*x^0

%e There is 1 permutation (the identity) with 0 inversions,

%e 3 permutations with 1 inversion, 5 with 2 inversions,

%e 6 with 3 inversions (the most frequent, marked with (*) ), 5 with 4 inversions, 3 with 5 inversions, and one with 6 inversions. (End)

%e G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 101*x^6 + 573*x^7 + 3836*x^8 + ...

%p f := 1: for n from 0 to 40 do f := f*add(x^i, i=0..n): s := series(f, x, n*(n+1)/2+1): m := max(coeff(s, x, j) $ j=0..n*(n+1)/2): printf(`%d,`,m) od: # from _James A. Sellers_, Dec 07 2000 [offset is off by 1 - _N. J. A. Sloane_, May 23 2006]

%p P:= [1]: a[1]:= 1:

%p for n from 2 to 100 do

%p P:= expand(P * add(x^j,j=0..n-1));

%p a[n]:= max(eval(convert(P,list),x=1));

%p od:

%p seq(a[i],i=1..100); # _Robert Israel_, Dec 14 2014

%t f[n_] := Max@ CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n-1}], x]; Array[f, 20]

%t Flatten[{1, 1, Table[Coefficient[Expand[Product[Sum[x^k, {k, 0, m-1}], {m, 1, n}]], x^Floor[n*(n-1)/4]], {n, 3, 20}]}] (* _Vaclav Kotesovec_, May 13 2016 *)

%t Table[SeriesCoefficient[QPochhammer[x, x, n]/(1-x)^n, {x, 0, Floor[n*(n-1)/4]}], {n, 1, 20}] (* _Vaclav Kotesovec_, May 13 2016 *)

%o (PARI)

%o a(n)=

%o /* return largest coefficient in product (1)(x+1)(x^2+x+1)...(x^(n-1)+...+x+1) */

%o { local(p,v);

%o p=prod(k=1,n-1,sum(j=0,k,x^j)); /* polynomial */

%o v=Vec(p); /* vector of coefficients */

%o v=vecsort(v); /* sort so largest is last element */

%o return(v[#v]); /* return last == largest */

%o }

%o vector(22,n,a(n)) /* _Joerg Arndt_, Jan 16 2011 */

%o (MAGMA) /* based on _David W. Wilson_'s formula */ PS<x>:=PowerSeriesRing(Integers()); [ Max(Coefficients(&*[&+[ x^i: i in [0..j] ]: j in [0..n-1] ])): n in [1..21] ]; // _Klaus Brockhaus_, Jan 18 2011

%o (PARI) {a(n) = if( n<0, 0, vecmax( Vec( prod(k=1, n, 1 - x^k) / (1 - x)^n)))}; /* _Michael Somos_, Apr 21 2014 */

%Y Row maxima of A008302.

%Y Odd terms are A186888.

%Y Cf. A128566.

%K nonn,easy,core,nice

%O 1,3

%A _N. J. A. Sloane_

%E Edited by _N. J. A. Sloane_, Mar 05 2011

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 March 23 17:19 EDT 2019. Contains 321432 sequences. (Running on oeis4.)