

A000140


KendallMann numbers: the most common number of inversions in a permutation on n letters is floor(n*(n1)/4); a(n) is the number of permutations with this many inversions.
(Formerly M1665 N0655)


16



1, 1, 2, 6, 22, 101, 573, 3836, 29228, 250749, 2409581, 25598186, 296643390, 3727542188, 50626553988, 738680521142, 11501573822788, 190418421447330, 3344822488498265, 62119523114983224, 1214967840930909302, 24965661442811799655, 538134522243713149122
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Row maxima of A008302, see example.
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).
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 2subsequences are as close to each other as possible, i.e., 0 or 1. We call such permutations 2balanced.
If 4n(n1) then (with A and D as above) the feasible values of AD are C(n,2), C(n,2)2,...,2,0,2,...,C(n,2), whereas if 4 does not divide n(n1), AD may equal C(n,2), C(n,2)2,...,1,1,...,C(n,2). Let a_n(i) equal the number of permutations with AD the ith highest feasible value.
The sequence in question gives the number of permutations for which AD=0 or AD=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(i1) + a_{n1}(i) for 1 <= i <= n and a_n(n+k) = a_n(n+k1) + a_{n1}(n+k)  a_n(k) for k >= 1. (End)
The only two primes found < 301 are for n = 3 and 6.
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
Named after the British statistician Maurice George Kendall (19071983) and the AustrianAmerican mathematician Henry Berthold Mann (19052000).  Amiram Eldar, Apr 07 2023


REFERENCES

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

Largest coefficient of (1)(x+1)(x^2+x+1)...(x^(n1) + ... + x + 1).  David W. Wilson
The number of terms is given in A000124.
Asymptotics (Mikhail Gaichenkov, 2010): a(n) ~ 6 * n^(n1) / exp(n).  Vaclav Kotesovec, May 17 2015


EXAMPLE

a(4) = 6 because the among the permutations of 4 elements those with 3 inversions are the most frequent and appear 6 times:
[inv. table] [permutation] number of inversions
0: [ 0 0 0 ] [ 0 1 2 3 ] 0
1: [ 1 0 0 ] [ 1 0 2 3 ] 1
2: [ 0 1 0 ] [ 0 2 1 3 ] 1
3: [ 1 1 0 ] [ 2 0 1 3 ] 2
4: [ 0 2 0 ] [ 1 2 0 3 ] 2
5: [ 1 2 0 ] [ 2 1 0 3 ] 3 (*)
6: [ 0 0 1 ] [ 0 1 3 2 ] 1
7: [ 1 0 1 ] [ 1 0 3 2 ] 2
8: [ 0 1 1 ] [ 0 3 1 2 ] 2
9: [ 1 1 1 ] [ 3 0 1 2 ] 3 (*)
10: [ 0 2 1 ] [ 1 3 0 2 ] 3 (*)
11: [ 1 2 1 ] [ 3 1 0 2 ] 4
12: [ 0 0 2 ] [ 0 2 3 1 ] 2
13: [ 1 0 2 ] [ 2 0 3 1 ] 3 (*)
14: [ 0 1 2 ] [ 0 3 2 1 ] 3 (*)
15: [ 1 1 2 ] [ 3 0 2 1 ] 4
16: [ 0 2 2 ] [ 2 3 0 1 ] 4
17: [ 1 2 2 ] [ 3 2 0 1 ] 5
18: [ 0 0 3 ] [ 1 2 3 0 ] 3 (*)
19: [ 1 0 3 ] [ 2 1 3 0 ] 4
20: [ 0 1 3 ] [ 1 3 2 0 ] 4
21: [ 1 1 3 ] [ 3 1 2 0 ] 5
22: [ 0 2 3 ] [ 2 3 1 0 ] 5
23: [ 1 2 3 ] [ 3 2 1 0 ] 6
The statistics are reflected by the coefficients of the polynomial
(1+x)*(1+x+x^2)*(1+x+x^2+x^3) ==
x^6 + 3*x^5 + 5*x^4 + 6*x^3 + 5*x^2 + 3*x^1 + 1*x^0
There is 1 permutation (the identity) with 0 inversions,
3 permutations with 1 inversion, 5 with 2 inversions,
6 with 3 inversions (the most frequent, marked with (*) ), 5 with 4 inversions, 3 with 5 inversions, and one with 6 inversions. (End)
G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 101*x^6 + 573*x^7 + 3836*x^8 + ...


MAPLE

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:= [1]: a[1]:= 1:
for n from 2 to 100 do
P:= expand(P * add(x^j, j=0..n1));
a[n]:= max(eval(convert(P, list), x=1));
od:


MATHEMATICA

f[n_] := Max@ CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n1}], x]; Array[f, 20]
Flatten[{1, 1, Table[Coefficient[Expand[Product[Sum[x^k, {k, 0, m1}], {m, 1, n}]], x^Floor[n*(n1)/4]], {n, 3, 20}]}] (* Vaclav Kotesovec, May 13 2016 *)
Table[SeriesCoefficient[QPochhammer[x, x, n]/(1x)^n, {x, 0, Floor[n*(n1)/4]}], {n, 1, 20}] (* Vaclav Kotesovec, May 13 2016 *)


PROG

(PARI)
a(n)=
/* return largest coefficient in product (1)(x+1)(x^2+x+1)...(x^(n1)+...+x+1) */
{ local(p, v);
p=prod(k=1, n1, sum(j=0, k, x^j)); /* polynomial */
v=Vec(p); /* vector of coefficients */
v=vecsort(v); /* sort so largest is last element */
return(v[#v]); /* return last == largest */
}
(Magma) /* based on David W. Wilson's formula */ PS<x>:=PowerSeriesRing(Integers()); [ Max(Coefficients(&*[&+[ x^i: i in [0..j] ]: j in [0..n1] ])): n in [1..21] ]; // Klaus Brockhaus, Jan 18 2011
(PARI) {a(n) = if( n<0, 0, vecmax( Vec( prod(k=1, n, 1  x^k) / (1  x)^n)))}; /* Michael Somos, Apr 21 2014 */
(Python)
from math import prod
from sympy import Poly
from sympy.abc import x
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


CROSSREFS



KEYWORD

nonn,easy,core,nice


AUTHOR



EXTENSIONS



STATUS

approved



