|
%I M1665 N0655 #156 Jan 31 2024 10:30:39
%S 1,1,2,6,22,101,573,3836,29228,250749,2409581,25598186,296643390,
%T 3727542188,50626553988,738680521142,11501573822788,190418421447330,
%U 3344822488498265,62119523114983224,1214967840930909302,24965661442811799655,538134522243713149122
%N Kendall-Mann numbers: the most common 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 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
%C Named after the British statistician Maurice George Kendall (1907-1983) and the Austrian-American mathematician Henry Berthold Mann (1905-2000). - _Amiram Eldar_, Apr 07 2023
%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 Dorin Andrica and Ovidiu Bagdasar, <a href="http://hdl.handle.net/10545/623501">On some results concerning the polygonal polynomials</a>, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
%H Dominique 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 Mikhail Gaichenkov, <a href="http://mathoverflow.net/questions/46368/the-property-of-kendall-mann-numbers">The property of Kendall-Mann numbers</a>, MathOverflow, 2010.
%H Richard 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 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
%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: # _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 (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 */
%o (Python)
%o from math import prod
%o from sympy import Poly
%o from sympy.abc import x
%o def A000140(n): return 1 if n == 1 else max(Poly(prod(sum(x**i for i in range(j+1)) for j in range(n))).all_coeffs()) # _Chai Wah Wu_, Feb 02 2022
%Y Row maxima of A008302.
%Y Odd terms are A186888.
%Y Cf. A000124, A001147, A128566, A181609.
%K nonn,easy,core,nice
%O 1,3
%A _N. J. A. Sloane_
%E Edited by _N. J. A. Sloane_, Mar 05 2011
| 