|
| |
|
|
A000140
|
|
Kendall-Mann numbers: the maximal number of inversions in a permutation on n letters is floor(n(n-1)/4); a(n) = number of permutations with this many inversions.
(Formerly M1665 N0655)
|
|
11
| |
|
|
1, 1, 2, 6, 22, 101, 573, 3836, 29228, 250749, 2409581, 25598186, 296643390, 3727542188, 50626553988, 738680521142, 11501573822788, 190418421447330, 3344822488498265, 62119523114983224, 1214967840930909302
(list; graph; refs; listen; history; 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).
Comments from Ryen Lapham and Anant Godbole (zrcl9(AT)imail.etsu.edu), Dec 12 2006: (Start) "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 {n choose 2}, {n choose 2}-2,....,2,0,-2,.....-{n choose 2}, whereas if 4 does not divide n(n-1), A-D may equal {n choose 2}, {n choose 2}-2,....,1,-1,.....-{n choose 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(({n choose 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 & 6.
|
|
|
REFERENCES
| F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
D. Foata, Distributions eule'riennes et mahoniennes sur le group des permutations, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.
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).
A. Waksman, On the complexity of inversions, IEEE Trans. Computers, 19 (1970), 1225-1226.
|
|
|
LINKS
| N. J. A. Sloane, Table of n, a(n) for n = 1..61
Wikipedia, q-Pochhammer symbol - Paul Muljadi (paulmuljadi(AT)yahoo.com), Jan 18 2011
Robert G. Wilson v, Table of n, a(n) for n = 1..350
Index entries for "core" sequences
|
|
|
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.
|
|
|
EXAMPLE
| From Joerg Arndt, 16 Jan 2011 (Start)
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)
|
|
|
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: # from James A. Sellers Dec 07 2000 [offset is off by 1 - N. J. A. Sloane (njas(AT)research.att.com), May 23 2006]
|
|
|
MATHEMATICA
| f[n_] := Max@ CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n-1}], x]; Array[f, 20]
|
|
|
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 */
}
vector(22, n, a(n)) /* show terms 1..22 */ /* From Joerg Arndt, Jan 16 2011 */
(MAGMA) /* based on D. 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
|
|
|
CROSSREFS
| Row maxima of A008302. Odd terms are A186888.
Sequence in context: A012268 A009655 A002772 * A079263 A129815 A103941
Adjacent sequences: A000137 A000138 A000139 * A000141 A000142 A000143
|
|
|
KEYWORD
| nonn,easy,core,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Edited by N. J. A. Sloane, Mar 05 2011
|
| |
|
|
