%I A008302
%S A008302 1,1,1,1,2,2,1,1,3,5,6,5,3,1,1,4,9,15,20,22,20,15,9,4,1,1,5,14,29,
%T A008302 49,71,90,101,101,90,71,49,29,14,5,1,1,6,20,49,98,169,259,359,455,
%U A008302 531,573,573,531,455,359,259,169,98,49,20,6,1
%N A008302 Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product 
               (1+x+...+x^k); k=1..n.
%C A008302 T(n,k) = number of permutations of {1..n} with k inversions.
%C A008302 n-th row gives growth series for symmetric group S_n with respect to 
               transpositions (1,2), (2,3), ..., (n-1,n).
%C A008302 T(n,k) = number of permutations of (1,2,...,n) having disorder equal 
               to k. The disorder of a permutation p of (1,2,...,n) is defined in 
               the following manner. We scan p from left to right as often as necessary 
               until all its elements are removed in increasing order, scoring one 
               point for each occasion on which an element is passed over and not 
               removed. The disorder of p is the number of points scored by the 
               end of the scanning and removal process. For example, the disorder 
               of (3,5,2,1,4) is 8, since on the first scan, 3,5,2 and 4 are passed 
               over, on the second, 3,5 and 4 and on the third scan, 5 is once again 
               not removed. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 09 
               2004
%C A008302 T(n,k)=number of permutations p=(p(1),...p(n)) of {1..n} such that Sum(i: 
               p(i)>p(i+1))=k (k is called the Major index of p). Example: T(3,0)=1, 
               T(3,1)=2,T(3,2)=2,T(3,3)=1 because the Major indices of the permutations 
               (1,2,3), (2,1,3),(3,1,2),(1,3,2),(2,3,1) and (3,2,1) are 0,1,1,2,
               2 and 3, respectively. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Aug 17 2004
%C A008302 T(n,k) = number of 2 x c matrices with column totals 1,2,3,...,n and 
               row totals k and (n+1 choose 2) - k. - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), 
               Jan 13 2006
%C A008302 T(n,k) is the number of permutations p of {1,2,...,n} for which den(p)=k. 
               Here den is the Denert statistic, defined in the following way: let 
               p=p(1)p(2)...p(n) be a permutation of {1,2,...,n}; if p(i)>i, then 
               we say that i is an excedance of p; let i_1 < i_2 < ... < i_k be 
               the excedances of p and let j_1 < j_2 < ... < j_{n-k} be the non-excedances 
               of p; let Exc(p) = p(i_1)p(i_2)...p(i_k), Nexc(p)=p(j_1)p(j_2)...p(j_{n-k}); 
               then, by definition den(p)=i_1 + i_2 + ... + i_k + inv(Exc(p)) + 
               inv(Nexc(p)), where inv denotes "number of inversions". Example: 
               T(4,5)=3 because we have 1342, 3241 and 4321. We show that den(4321)=5: 
               the excedances are 1 and 2; Exc(4321)=43, Nexc(4321)=21; now den(4321)=1+2+inv(43)+inv(21)=3+1+1=5. 
               [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 29 2008]
%D A008302 M. Bona, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, 
               Florida, 2004 (p. 52).
%D A008302 L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math. J. Volume 
               15, Number 4 (1948), 987-1000. See http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&han\
               dle=euclid.dmj/1077475200 [from Roger L. Bagula (rlbagulatftn(AT)yahoo.com), 
               Feb 06 2009]
%D A008302 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.
%D A008302 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied 
               Tables, Cambridge, 1966, p. 241.
%D A008302 E. Deutsch, Problem 10975, Amer. Math. Monthly, 111 (2004), 541.
%D A008302 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 A008302 D. Foata and D. Zeilberger, Denert's permutation statistic is indeed 
               Euler-Mahonian, Studies in Appl. Math., 83(1990),31-59. [From Emeric 
               Deutsch (deutsch(AT)duke.poly.edu), Oct 29 2008]
%D A008302 Guo-Niu Han, Une nouvelle bijection pour la statistique de Denert, C. 
               R. Acad. Sci. Paris, Ser. I, 310(1990),493-496. [From Emeric Deutsch 
               (deutsch(AT)duke.poly.edu), Oct 29 2008]
%D A008302 P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 
               2000, p. 163, top display.
%D A008302 A. Mendes, A note on alternating permutations, Amer. Math. Monthly, 114 
               (2007), 437-440.
%D A008302 R. H. Moritz and R. C. Williams, A coin-tossing problem and some related 
               combinatorics, Math. Mag., 61 (1988), 24-29.
%D A008302 E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, 
               p. 96.
%D A008302 R. P. Stanley, Binomial posets, Moebius inversion and permutation enumeration, 
               J. Combinat. Theory, A 20 (1976), 336-356.
%D A008302 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see 
               Corollary 1.3.10, p. 21.
%H A008302 T. D. Noe, <a href="b008302.txt">Rows n=0..30 of triangle, flattened</
               a>
%H A008302 B. H. Margolius, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Permutations with inversions</a>, J. Integ. Seqs. Vol. 4 (2001), 
               #01.2.4.
%H A008302 Thomas Wieder, <a href="a008302.txt">Comments on A008302</a>
%F A008302 Comtet and Moritz-Williams give recurrences.
%F A008302 Mendes and Stanley give g.f.'s.
%F A008302 G.f.: Product_{j=1..n} (1-x^j)/(1-x) = Sum_{k=1..M} T{n, k} x^k, where 
               M = n(n-1)/2.
%e A008302 1; 1+x; (1+x)(1+x+x^2) = 1+2x+2x^2+x^3; etc.
%e A008302 {1},
%e A008302 {1, 1},
%e A008302 {1, 2, 2, 1},
%e A008302 {1, 3, 5, 6, 5, 3, 1},
%e A008302 {1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1},
%e A008302 {1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1},
%e A008302 {1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 
               259, 169, 98, 49, 20, 6, 1},
%e A008302 {1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 
               3836, 3736, 3450, 3017, 2493, 1940, 1415, 961, 602, 343, 174, 76, 
               27, 7, 1},
%e A008302 {1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, 11021, 14395, 
               17957, 21450, 24584, 27073, 28675, 29228, 28675, 27073, 24584, 21450, 
               17957, 14395, 11021, 8031, 5545, 3606, 2191, 1230, 628, 285, 111, 
               35, 8, 1},
%e A008302 {1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, 32683, 47043, 
               64889, 86054, 110010, 135853, 162337, 187959, 211089, 230131, 243694, 
               250749, 250749, 243694, 230131, 211089, 187959, 162337, 135853, 110010, 
               86054, 64889, 47043, 32683, 21670, 13640, 8095, 4489, 2298, 1068, 
               440, 155, 44, 9, 1}
%p A008302 g := proc(n,k) option remember; if k=0 then return(1) else if (n=1 and 
               k=1) then return(0) else if (k<0 or k>binomial(n,2)) then return(0) 
               else g(n-1,k)+g(n,k-1)-g(n-1,k-n) end if end if end if end proc;
%p A008302 BB:=j->1+sum(t^i, i=1..j): for n from 1 to 8 do Z[n]:=sort(expand(simplify(product(BB(j), 
               j=0..n-2)))) od: for n from 1 to 8 do seq(coeff(Z[n], t, j), j=0..(n-1)*(n-2)/
               2) od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 13 2007
%t A008302 p[x_, n_] = Product[(1 - x^k)/(1 - x), {k, 1, n}];
%t A008302 Table[FullSimplify[ExpandAll[p[x, n]]], {n, 0, 10}];
%t A008302 Table[CoefficientList[FullSimplify[ExpandAll[p[x, n]]], x], {n, 0, 10}];
%t A008302 Flatten[%] [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com), Feb 06 
               2009]
%Y A008302 Diagonals give A000707, A001892, A001893, A001894, A005283, A005284, 
               A005285, A005286, A005287, A005288.
%Y A008302 Row-maxima: A000140, Truncated table: A060701
%Y A008302 Sequence in context: A060351 A076037 A076263 this_sequence A131791 A010358 
               A155865
%Y A008302 Adjacent sequences: A008299 A008300 A008301 this_sequence A008303 A008304 
               A008305
%K A008302 easy,tabf,nonn,nice,new
%O A008302 0,6
%A A008302 N. J. A. Sloane (njas(AT)research.att.com).
%E A008302 Maple code from Barbara Haas Margolius (margolius(AT)math.csuohio.edu) 
               5/31/01
%E A008302 There were some mistaken edits to this entry (inclusion of an initial 
               1, etc.) which I undid. - njas, Nov 30 2009