|
|
A000140
|
|
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.
(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 2-subsequences are as close to each other as possible, i.e., 0 or 1. We call such permutations 2-balanced.
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.
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)
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 (1907-1983) and the Austrian-American mathematician Henry Berthold Mann (1905-2000). - 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^(n-1) + ... + x + 1). - David W. Wilson
The number of terms is given in A000124.
Asymptotics (Mikhail Gaichenkov, 2010): a(n) ~ 6 * n^(n-1) / 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..n-1));
a[n]:= max(eval(convert(P, list), x=1));
od:
|
|
MATHEMATICA
|
f[n_] := Max@ CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n-1}], x]; Array[f, 20]
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 *)
Table[SeriesCoefficient[QPochhammer[x, x, n]/(1-x)^n, {x, 0, Floor[n*(n-1)/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^(n-1)+...+x+1) */
{ local(p, v);
p=prod(k=1, n-1, 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..n-1] ])): 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
|
|
|
|