This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008302 Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1). 91


%S 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,49,

%T 71,90,101,101,90,71,49,29,14,5,1,1,6,20,49,98,169,259,359,455,531,

%U 573,573,531,455,359,259,169,98,49,20,6,1,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,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

%N Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1).

%C T(n,k) = number of permutations of {1..n} with k inversions.

%C n-th row gives growth series for symmetric group S_n with respect to transpositions (1,2), (2,3), ..., (n-1,n).

%C 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_, Jun 09 2004

%C 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_, Aug 17 2004

%C T(n,k) = number of 2 X c matrices with column totals 1,2,3,...,n and row totals k and binomial(n+1,2) - k. - _Mitch Harris_, Jan 13 2006

%C 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. - _Emeric Deutsch_, Oct 29 2008

%C T(n,k) is the number of size k submultisets of the multiset {1,2,2,3,3,3,...,n-1} (which contains i copies of i for 0 < i < n).

%C The limit of products of the numbers of fixed necklaces of length n composed of beads of types N(n,a), n--> infinity, is the generating function for inversions (we must exclude one unimportant factor a^n/n!). The error is < a^n/n!*O(1/n^(1/2-epsilon)). See Gaichenkov link. - _Mikhail Gaichenkov_, Aug 27 2012

%C The number of ways to distribute k-1 indistinguishable balls into n-1 boxes of capacity 1,2,3,...n-1. - _Andrew Woods_, Sep 26 2012

%C Partial sums of rows give triangle A161169. - _András Salamon_, Feb 16 2013

%C The number of permutations of n that require k pair swaps in the bubble sort to sort them into the natural 1,2,...,n order. - _R. J. Mathar_, May 04 2013

%C Also series coefficients of q-factorial [n]_q ! - see Mathematica line. - _Wouter Meeussen_, Jul 12 2014

%C From _Mikhail Gaichenkov_, Aug 16 2016: (Start)

%C Following asymptotic expansions in the Central Limit Theorem developed by Valentin V. Petrov, the cumulative distribution function of these numbers, CDF_N(x), is equal to the CDF of the normal distribution - (0.06/sqrt(2Pi))*exp(-x^2/2)(x^3-3x)*(6N^3+21N^2+31N+31)/(N(2N+5)^2(N-1)+O(1/N^2).

%C This can be written as: CDF of the normal distribution -(0.09/(N*sqrt(2Pi)))*exp(-x^2/2)He_3(x) + O(1/N^2), N > 1, natural numbers (Gaichenkov, private research).

%C According to B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4, "the unimodal behavior of the inversion numbers suggests that the number of inversions in a random permutation may be asymptotically normal". See links.

%C Moreover, E. Ben-Naim (Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory), "On the Mixing of Diffusing Particles" (13 Oct 2010), states that the Mahonian Distribution becomes a function of a single variable for large numbers of element, i.e., the probability distribution function is normal. See links.

%C To be more precise the expansion of the distribution is presented for a finite number of elements (or particles in terms of E. Ben-Naim's article). The distribution tends to the normal distribution for an infinite numbers of elements.

%C (End)

%D M. Bona, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004 (p. 52).

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.

%D P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 163, top display.

%D E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.

%D Valentin V. Petrov, Sums of Independent Random Variables, Springer Berlin Heidelberg, 1975, p. 134.

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Corollary 1.3.10, p. 21.

%H Alois P. Heinz, <a href="/A008302/b008302.txt">Rows n = 1..50, flattened</a> (first 30 rows from Paul D. Hanna)

%H F. N. David, M. G. Kendall and D. E. Barton, <a href="/A005288/a005288.pdf">Symmetric Function and Allied Tables</a>, Cambridge, 1966, p. 241-242. (Annotated scanned copy)

%H E. Ben-Naim, <a href="https://arxiv.org/abs/1010.2563">On the Mixing of Diffusing Particles</a>, arXiv:1010.2563 [cond-mat.stat-mech], 2010.

%H F. Brglez, <a href="http://ev.fe.uni-lj.si/4-2011/Brglez.pdf">Of n-dimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction</a>, Elektrotehniski Vestnik, 78(4): 181-192, 2011.

%H Agnieszka Bukietyńska, <a href="http://ceejme.eu/wp-content/uploads/2018/02/ceejme_3_7_art_01.pdf">The test of inversion in the analysis of investment funds</a>, Central and Eastern European Journal of Management and Economics, Vol. 5, No. 3, 277-289, September 2017.

%H L. Carlitz, <a href="http://dx.doi.org/10.1215/S0012-7094-48-01588-9">q-Bernoulli numbers and polynomials</a>, Duke Math. J. Volume 15, Number 4 (1948), 987-1000.

%H Luke Chamandy, Anvar Shukurov, A. Russ Taylor, <a href="https://arxiv.org/abs/1609.05688">Statistical tests of galactic dynamo theory</a>, arXiv:1609.05688 [astro-ph.GA], 2016.

%H Mariusz Czekala and Agnieszka Bukietyńska, <a href="https://doi.org/10.1007/978-3-319-46589-0_14">Distribution of Inversions and the Power of the τ-Kendall's Test</a>, in J. Świątek, Z. Wilimowska, L. Borzemski, A. Grzech (eds), Information Systems Architecture and Technology: Proceedings of 37th International Conference on Information Systems Architecture and Technology - ISAT 2016 - Part III, pp. 175-185.

%H E. Deutsch, <a href="http://www.jstor.org/stable/4145088">Problem 10975: Enumeration of Permutations by Disorder</a>, Amer. Math. Monthly, 111 (2004), 541.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000156/">The Denert index of a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000004/">The major index of a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000018">The number of inversions of a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000224/">The sorting index of a permutation</a>

%H D. Foata, <a href="http://dx.doi.org/10.1007/978-94-010-1220-1_2">Distributions eulériennes et mahoniennes sur le groupe des permutations</a>, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.

%H D. Foata and D. Zeilberger, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub63.html">Denert's permutation statistic is indeed Euler-Mahonian</a>, Studies in Appl. Math., 83(1990),31-59. [From _Emeric Deutsch_, Oct 29 2008]

%H Mikhail Gaichenkov, <a href="http://mathoverflow.net/questions/103716/necklaces-and-the-generating-function-for-inversions">Necklaces and the generating function for inversions</a>

%H Mikhail Gaichenkov, <a href="http://mathoverflow.net/questions/157316/pros-and-cons-of-probability-model-for-permutations">Pros and cons of probability model for permutations</a>

%H Amy Grady, <a href="http://www.etsu.edu/cas/math/pp2014/documents/talks/grady.pdf">Sorting index and Mahonian-Stirling pairs for labeled forests</a>, Clemson University, July 10, 2014.

%H R. K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>

%H Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p02nbiject.pdf">Une nouvelle bijection pour la statistique de Denert</a>, C. R. Acad. Sci. Paris, Ser. I, 310(1990),493-496.

%H Stuart A. Hannah, <a href="http://arxiv.org/abs/1502.05340">Sieved Enumeration of Interval Orders and Other Fishburn Structures</a>, arXiv:1502.05340 [math.CO], (18-February-2015).

%H Y.-H. He, C. Matti, C. Sun, <a href="http://arxiv.org/abs/1403.6833">The Scattering Variety</a>, arXiv preprint arXiv:1403.6833 [hep-th], 2014.

%H E. Irurozki, <a href="http://www.sc.ehu.es/ccwbayes/isg/administrator/components/com_jresearch/files/theses/tesis_ekhine_irurozki.pdf">Sampling and learning distance-based probability models for permutation spaces</a>, PhD Dissertation, Department of Computer Science and Artificial Intelligence of the University of the Basque Country, 2015.

%H E. Irurozki, B. Calvo, J. A. Lozano, <a href="https://addi.ehu.es/bitstream/10810/11238/1/tr14-5.pdf">An R package for permutations, Mallows and Generalized Mallows models</a>, 2014.

%H Ekhine Irurozki, B. Calvo, J. A. Lozano, <a href="http://dx.doi.org/10.18637/jss.v071.i12">PerMallows: An R Package for Mallows and Generalized Mallows Models</a>, Journal of Statistical Software, August 2016, Volume 71, Issue 12. doi: 10.18637/jss.v071.i12

%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic2/janjic53.html">A Generating Function for Numbers of Insets</a>, Journal of Integer Sequences, 17, 2014, #14.9.7.

%H J. A. Koziol, <a href="http://dx.doi.org/10.1002/cem.2504">Sums of ranking differences and inversion numbers for method discrimination</a>, Journal of Chemometrics, 27 (2013): 165-169. doi: 10.1002/cem.2504

%H B. H. Margolius, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/inversions.html">Permutations with inversions</a>, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.

%H J. L. Martin and J. D. Wagner, <a href="http://arxiv.org/abs/1209.3493">On the Spectra of Simplicial Rook Graphs</a>, arXiv preprint arXiv:1209.3493 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 27 2012

%H A. Mendes, <a href="http://www.jstor.org/stable/27642223">A note on alternating permutations</a>, Amer. Math. Monthly, 114 (2007), 437-440.

%H R. H. Moritz and R. C. Williams, <a href="http://www.jstor.org/stable/2690326">A coin-tossing problem and some related combinatorics</a>, Math. Mag., 61 (1988), 24-29.

%H E. Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.

%H E. Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.

%H Michal Opler, <a href="http://arxiv.org/abs/1505.07135">Major index distribution over permutation classes</a>, arXiv:1505.07135 [math.CO], 2015.

%H O. Patashnik, <a href="/A008302/a008302.pdf">Letter to R. H. Moritz & R. C. Williams, cc N. J. A. Sloane, Oct 1988</a>

%H Nikolay L. Poliakov, <a href="https://arxiv.org/abs/1606.04816">Note on level r consensus</a>, arXiv preprint arXiv:1606.04816 [q-fin.EC], 2016.

%H Svetlana Poznanovic, <a href="http://doi.org/10.1016/j.jcta.2014.03.007">The sorting index and equidistribution of set-valued statistics over restricted permutations</a>, Journal of Combinatorial Theory, Series A, 125 (2014), 254-272.

%H R. P. Stanley, <a href="http://dx.doi.org/10.1016/0097-3165(76)90028-5">Binomial posets, Moebius inversion and permutation enumeration</a>, J. Combinat. Theory, A 20 (1976), 336-356.

%H A. Waksman, <a href="http://dx.doi.org/10.1109/T-C.1970.222866">On the complexity of inversions</a>, IEEE Trans. Computers, 19 (1970), 1225-1226. See Table II.

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/Necklace.html"> Mathworld: Necklace</a>

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/IrreduciblePolynomial.html">Mathworld: Irreducible Polynomial</a>

%H Thomas Wieder, <a href="/A008302/a008302.txt">Comments on A008302</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Major_index">Major index</a>

%F Comtet and Moritz-Williams give recurrences.

%F Mendes and Stanley give g.f.'s.

%F G.f.: Product_{j=1..n} (1-x^j)/(1-x) = Sum_{k=0..M} T{n, k} x^k, where M = n*(n-1)/2.

%F From _Andrew Woods_, Sep 26 2012: (Start)

%F T(1, 1) = 1, T(1, k != 1) = 0,

%F T(n, k) = Sum_{j=0..n-1} T(n-1, k-j),

%F T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n). (End)

%F E.g.f. satisfies: A(x,q) = 1 + Integral (A(x,q) - q*A(q*x,q))/(1-q) dx, where A(x,q) = Sum_{n>=0} x^n/n! * Sum_{k=0..n*(n-1)/2} T(n,k)*q^k, when T(0,0) = 1 is included. - _Paul D. Hanna_, Dec 31 2016

%e 1; 1+x; (1+x)*(1+x+x^2) = 1+2*x+2*x^2+x^3; etc.

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 2, 1;

%e 1, 3, 5, 6, 5, 3, 1;

%e 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1;

%e 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1;

%e 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1;

%e 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 ...

%p 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; # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

%p 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_, Apr 13 2007

%p # alternative Maple program:

%p b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,

%p add(b(u+j-1, o-j)*x^(u+j-1), j=1..o)+

%p add(b(u-j, o+j-1)*x^(u-j), j=1..u)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):

%p seq(T(n), n=1..10); # _Alois P. Heinz_, May 02 2017

%t f[n_] := CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n}], x]; Flatten[Array[f, 8, 0]]

%t nn = 25; T[1, 1] = 1; T[n_, 1] = 0; T[n_, k_] := T[n, k] = Sum[T[n - i, k - 1], {i, 1, k - 1}]; MatrixForm[Table[T[n, k], {n, nn}, {k, nn}]] (* _Mats Granvik_ and _Roger L. Bagula_, Jun 19 2011 *)

%t alternatively (versions 7 and up):

%t Table[CoefficientList[Series[QFactorial[n,q],{q,0,n(n-1)/2}],q],{n,9}] (* _Wouter Meeussen_, Jul 12 2014 *)

%o (Sage)

%o from sage.combinat.q_analogues import q_factorial

%o for n in (1..6): print q_factorial(n).list() # _Peter Luschny_, Jul 18 2016

%o (PARI) {T(n,k) = my(A=1+x); for(i=1,n, A = 1 + intformal(A - q*subst(A,x,q*x +x^2*O(x^n)))/(1-q)); polcoeff(n!*polcoeff(A,n,x),k,q)}

%o for(n=1,10, for(k=0,n*(n-1)/2, print1(T(n,k),", ")); print("")) \\ _Paul D. Hanna_, Dec 31 2016

%Y Diagonals give A000707, A001892, A001893, A001894, A005283, A005284, A005285, A005286, A005287, A005288, A242656, A242657.

%Y Row-maxima: A000140, truncated table: A060701, row sums: A000142.

%Y A161436 is one of the rows.

%Y A001809 gives total Denert index of all permutations.

%Y Cf. A139365.

%K easy,tabf,nonn,nice,look

%O 1,5

%A _N. J. A. Sloane_

%E There were some mistaken edits to this entry (inclusion of an initial 1, etc.) which I undid. - _N. J. A. Sloane_, Nov 30 2009

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 19 17:22 EDT 2018. Contains 305594 sequences. (Running on oeis4.)