Search: id:A000140
Results 1-1 of 1 results found.

%I A000140 M1665 N0655
%S A000140 1,1,2,6,22,101,573,3836,29228,250749,2409581,25598186,296643390,
%T A000140 3727542188,50626553988,738680521142,11501573822788,190418421447330,
%U A000140 3344822488498265,62119523114983224,1214967840930909302
%N A000140 Kendall-Mann numbers: the maximum number of permutations on n letters 
               having the same number of inversions (that is when the number of 
               inversions is floor((n choose 2)/2)).
%C A000140 Comments from Mitch Harris, Sep 18 2005: "The maximal number of inversions 
               in a permutation of n letters occurs uniquely in the reverse permutation, 
               where every pair is an inversion and the number of inversions here 
               is (n choose 2).
%C A000140 "What is really being described is the distribution of inversions and 
               so the function is from inversions to permutations. Finding the max 
               eliminates the quantified variable of inversion. So the function 
               (and therefore sequence) is from the index n (the number of letters 
               on which the permutations act) to the size of the set of permutations 
               all having the same number of inversions.
%C A000140 "For example, on 3 letters, inversion numbers 0, 1, 2 and 3 partition 
               the permutations into {123}, {132, 213}, {231, 312}, {321} respectively 
               and the largest of these is of size 2."
%C A000140 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.
%C A000140 "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.
%C A000140 "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)
%D A000140 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000140 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000140 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied 
               Tables, Cambridge, 1966, p. 241.
%D A000140 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.
%D A000140 A. Waksman, On the complexity of inversions, IEEE Trans. Computers, 19 
               (1970), 1225-1226.
%H A000140 N. J. A. Sloane, <a href="b000140.txt">Table of n, a(n) for n = 1..61</
               a>
%H A000140 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A000140 Largest coefficient of (1)(x+1)(x^2+x+1)...(x^n+...+x+1) (David W. Wilson).
%p A000140 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]
%Y A000140 Row maxima of A008302.
%Y A000140 Sequence in context: A012268 A009655 A002772 this_sequence A079263 A129815 
               A103941
%Y A000140 Adjacent sequences: A000137 A000138 A000139 this_sequence A000141 A000142 
               A000143
%K A000140 nonn,easy,core,nice
%O A000140 1,3
%A A000140 N. J. A. Sloane (njas(AT)research.att.com).

Search completed in 0.002 seconds