This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A008302 #403 Apr 21 2025 09:38:49
%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,49,
%T A008302 71,90,101,101,90,71,49,29,14,5,1,1,6,20,49,98,169,259,359,455,531,
%U A008302 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 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). Also enumerates permutations by their major index.
%C A008302 T(n,k) is the 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) is the 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 A008302 T(n,k) is the 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 A008302 T(n,k) is the 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 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. - _Emeric Deutsch_, Oct 29 2008
%C A008302 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 A008302 The limit of products of the numbers of fixed necklaces of length n composed of beads of types N(n,b), n --> infinity, is the generating function for inversions (we must exclude one unimportant factor b^n/n!). The error is < (b^n/n!)*O(1/n^(1/2-epsilon)). See Gaichenkov link. - _Mikhail Gaichenkov_, Aug 27 2012
%C A008302 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 A008302 Partial sums of rows give triangle A161169. - _András Salamon_, Feb 16 2013
%C A008302 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 A008302 Also series coefficients of q-factorial [n]_q ! -- see Mathematica line. - _Wouter Meeussen_, Jul 12 2014
%C A008302 From _Mikhail Gaichenkov_, Aug 16 2016: (Start)
%C A008302 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(2*Pi))*exp(-x^2/2)(x^3-3x)*(6N^3+21N^2+31N+31)/(N(2N+5)^2(N-1)+O(1/N^2).
%C A008302 This can be written as: CDF of the normal distribution -(0.09/(N*sqrt(2*Pi)))*exp(-x^2/2)*He_3(x) + O(1/N^2), N > 1, natural numbers (Gaichenkov, private research).
%C A008302 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 A008302 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 A008302 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 A008302 (End)
%C A008302 T(n,k) statistic counts (labeled) permutation graphs with n vertices and k edges. - _Mikhail Gaichenkov_, Aug 20 2019
%C A008302 From _Gus Wiseman_, Aug 12 2020: (Start)
%C A008302 Number of divisors of A006939(n - 1) or A076954(n - 1) with k prime factors, counted with multiplicity, where A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1). For example, row n = 4 counts the following divisors:
%C A008302 1 2 4 8 24 72 360
%C A008302 3 6 12 36 120
%C A008302 5 9 18 40 180
%C A008302 10 20 60
%C A008302 15 30 90
%C A008302 45
%C A008302 Crossrefs:
%C A008302 A336420 is the case with distinct prime multiplicities.
%C A008302 A006939 lists superprimorials or Chernoff numbers.
%C A008302 A022915 counts permutations of prime indices of superprimorials.
%C A008302 A317829 counts factorizations of superprimorials.
%C A008302 A336941 counts divisor chains under superprimorials.
%C A008302 Cf. A000005, A001222, A008278, A022559, A027423, A076954, A181796.
%C A008302 (End)
%C A008302 Named after the British mathematician Percy Alexander MacMahon (1854-1929). - _Amiram Eldar_, Jun 13 2021
%C A008302 Row maxima ~ n!/(sigma * sqrt(2*Pi)), sigma^2 = (2*n^3 + 9*n^2 + 7*n)/72 = variance of group type A_n (see also A161435). - _Mikhail Gaichenkov_, Feb 08 2023
%C A008302 Sum_{i>=0} T(n,i)*k^i = A069777(n,k). - _Geoffrey Critzer_, Feb 26 2025
%D A008302 Miklós Bóna, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004 (p. 52).
%D A008302 Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.
%D A008302 Florence Nightingale David, Maurice George Kendall, and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
%D A008302 Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 163, top display.
%D A008302 Eugen Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
%D A008302 Valentin V. Petrov, Sums of Independent Random Variables, Springer Berlin Heidelberg, 1975, p. 134.
%D A008302 Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Corollary 1.3.10, p. 21.
%H A008302 Alois P. Heinz, <a href="/A008302/b008302.txt">Rows n = 1..50, flattened</a> (first 30 rows from Paul D. Hanna)
%H A008302 Ashleigh Adams, Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker, and Amanda Welch, <a href="https://arxiv.org/abs/2402.16251">Cyclic sieving on permutations - an analysis of maps and statistics in the FindStat database</a>, arXiv:2402.16251 [math.CO], 2024. See p. 7.
%H A008302 Dorin Andrica and Ovidiu Bagdasar, <a href="https://doi.org/10.37193/CJM.2019.01.01">On some results concerning the polygonal polynomials</a>, Carpathian Journal of Mathematics, Vol. 35, No. 1 (2019), pp. 1-11.
%H A008302 Hasan Arslan, <a href="https://arxiv.org/abs/2404.05099">A combinatorial interpretation of Mahonian numbers of type B</a>, arXiv:2404.05099 [math.CO], 2024. See p. 3.
%H A008302 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 A008302 David J. Benson, <a href="https://arxiv.org/abs/2407.21175">The cohomology of the nilCoxeter algebra</a>, arXiv:2407.21175 [math.RA], 2024. See p. 4.
%H A008302 Sara C. Billey, Matjaž Konvalinka, and Joshua P. Swanson, <a href="https://arxiv.org/abs/1809.07386">Tableaux posets and the fake degrees of coinvariant algebras</a>, arXiv:1809.07386 [math.CO], 2018.
%H A008302 Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier, <a href="https://arxiv.org/abs/2010.09678">On the Robustness of Winners: Counting Briberies in Elections</a>, arXiv:2010.09678 [cs.GT], 2020.
%H A008302 Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, and Stanisław Szufa, <a href="https://arxiv.org/abs/2105.07815">Putting a Compass on the Map of Elections</a>, arXiv:2105.07815 [cs.GT], 2021.
%H A008302 J. Bourget, <a href="http://www.numdam.org/item/NAM_1871_2_10__254_1/">Des permutations</a>, Nouvelles annales de mathématiques, 2e série, tome 10 (1871), pp. 254-268.
%H A008302 Franc 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, Vol. 78, No. 4 (2011), pp. 181-192.
%H A008302 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 (September 2017), pp. 277-289.
%H A008302 L. Carlitz, <a href="http://dx.doi.org/10.1215/S0012-7094-48-01588-9">q-Bernoulli numbers and polynomials</a>, Duke Math. J., Vol. 15, No. 4 (1948), pp. 987-1000.
%H A008302 Luke Chamandy, Anvar Shukurov, and 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 A008302 Geoffrey Critzer, <a href="https://esirc.emporia.edu/handle/123456789/3595">Combinatorics of Vector Spaces over Finite Fields</a>, Master's thesis, Emporia State University, 2018.
%H A008302 Mariusz Czekała 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 A008302 Mariusz Czekała, Agnieszka Bukietyńska, and Agnieszka Matylda Schlichtinger, <a href="https://doi.org/10.1007/978-3-319-99993-7">Estimation of the Probability of Inversion in the Test of Variable Dependencies</a>, Information Systems Architecture and Technology: Proceedings of 39th International Conference on Information Systems Architecture and Technology (ISAT 2018), Part III, 145-156.
%H A008302 F. N. David, M. G. Kendall, and D. E. Barton, <a href="/A005288/a005288.pdf">Symmetric Function and Allied Tables</a>, Cambridge, 1966, pp. 241-242. (Annotated scanned copy)
%H A008302 Emeric Deutsch, <a href="http://www.jstor.org/stable/4145088">Problem 10975: Enumeration of Permutations by Disorder</a>, Amer. Math. Monthly, Vol. 111, No. 6 (2004), p. 541.
%H A008302 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 A008302 Dominique 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>, in: M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977, pp. 27-49.
%H A008302 Dominique Foata and Doron 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., Vol. 83 (1990), pp. 31-59. [From _Emeric Deutsch_, Oct 29 2008]
%H A008302 Víctor Franco-Sánchez, Arnau Martí-Llobet, and Ramon Ferrer-i-Cancho, <a href="https://arxiv.org/abs/2404.14192">Swap distance minimization beyond entropy minimization in word order variation</a>, arXiv:2404.14192 [cs.CL], 2024. See p. 34.
%H A008302 Mikhail Gaichenkov, <a href="http://mathoverflow.net/questions/103716/necklaces-and-the-generating-function-for-inversions">Necklaces and the generating function for inversions</a>, MathOverflow, 2012.
%H A008302 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>, MathOverflow, 2014.
%H A008302 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 A008302 Oğuz Gürerk, Ümit Işlak, and Mehmet Akif Yıldız, <a href="https://arxiv.org/abs/1901.06678">A study on random permutation graphs</a>, arXiv:1901.06678 [math.CO], 2019.
%H A008302 Richard K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>.
%H A008302 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, Vol. 310 (1990), pp. 493-496.
%H A008302 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 A008302 Yang-Hui He, Cyril Matti and Chuang Sun, <a href="http://arxiv.org/abs/1403.6833">The Scattering Variety</a>, arXiv preprint arXiv:1403.6833 [hep-th], 2014.
%H A008302 Ekhine 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 A008302 Ekhine Irurozki, Borja Calvo and José 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 A008302 Ekhine Irurozki, Borja Calvo and José 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, Vol. 71, No. 12 (August 2016).
%H A008302 Milan 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, Vol. 17 (2014), Article 14.9.7.
%H A008302 Thomas Kahle and Christian Stump, <a href="https://arxiv.org/abs/1802.01389">Counting inversions and descents of random elements in finite Coxeter groups</a>, arXiv:1802.01389 [math.CO], 2018-2019.
%H A008302 James 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, Vol. 27 (2013), pp. 165-169.
%H A008302 Barbara H. Margolius, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/inversions.html">Permutations with inversions</a>, J. Integ. Seq., Vol. 4 (2001), Article 01.2.4.
%H A008302 Jeremy L. Martin and Jennifer 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 A008302 Anthony Mendes, <a href="http://www.jstor.org/stable/27642223">A note on alternating permutations</a>, Amer. Math. Monthly, Vol. 114, No. 5 (2007), pp. 437-440.
%H A008302 Vinicus de Morais Alves, Rafael Dowsley, Rafael Timateo de Sousa, and Anderson C.A. Nascimento, <a href="https://researchmgt.monash.edu/ws/portalfiles/portal/363807369/353807076_oa.pdf">Information-Theoretically Secure String Commitments Based on Packet Reordering Channels</a>, IEEE Access, Volume 9 (2021), pp. 139931-139936.
%H A008302 Roger H. Moritz and Robert C. Williams, <a href="http://www.jstor.org/stable/2690326">A coin-tossing problem and some related combinatorics</a>, Math. Mag., Vol. 61, No. 1 (1988), pp. 24-29.
%H A008302 Eugen Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.
%H A008302 Eugen Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.
%H A008302 Juan Miguel Nieto, <a href="https://doi.org/10.1007/978-3-319-96020-3_7">Tailoring and Hexagon Form Factors</a>, Spinning Strings and Correlation Functions in the AdS/CFT Correspondence, Springer Theses (Recognizing Outstanding Ph.D. Research), Springer, Cham, 2018.
%H A008302 Michal Opler, <a href="http://arxiv.org/abs/1505.07135">Major index distribution over permutation classes</a>, arXiv:1505.07135 [math.CO], 2015.
%H A008302 Oren Patashnik, <a href="/A008302/a008302.pdf">Letter to R. H. Moritz & R. C. Williams, cc N. J. A. Sloane, Oct 1988</a>.
%H A008302 Michael Penn, <a href="https://www.youtube.com/watch?v=BkJW1O0cBJc">The Quantum Factorial is upon us.</a>, YouTube video, 2023.
%H A008302 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 A008302 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, Vol. 125 (2014), pp. 254-272.
%H A008302 Richard 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, Series A, Vol. 20, No. 3 (1976), pp. 336-356.
%H A008302 A. Waksman, <a href="http://dx.doi.org/10.1109/T-C.1970.222866">On the complexity of inversions</a>, IEEE Trans. Computers, Vol. 19 (1970), pp. 1225-1226. See Table II.
%H A008302 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Necklace.html">Necklace</a>.
%H A008302 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IrreduciblePolynomial.html">Irreducible Polynomial</a>.
%H A008302 Thomas Wieder, <a href="/A008302/a008302.txt">Comments on A008302</a>.
%H A008302 Wikipedia, <a href="https://en.wikipedia.org/wiki/Major_index">Major index</a>
%F A008302 Bourget, 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=0..M} T{n, k} x^k, where M = n*(n-1)/2.
%F A008302 From _Andrew Woods_, Sep 26 2012, corrected by _Peter Kagey_, Mar 18 2021: (Start)
%F A008302 T(1, 0) = 1,
%F A008302 T(n, k) = 0 for n < 0, k < 0 or k > n*(n-1)/2.
%F A008302 T(n, k) = Sum_{j=0..n-1} T(n-1, k-j),
%F A008302 T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n). (End)
%F A008302 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 A008302 1; 1+x; (1+x)*(1+x+x^2) = 1+2*x+2*x^2+x^3; etc.
%e A008302 Triangle begins:
%e A008302 n\k| 0 1 2 3 4 5 6 7 8 9 10
%e A008302 ---+--------------------------------------------------------------
%e A008302 1 | 1;
%e A008302 2 | 1, 1;
%e A008302 3 | 1, 2, 2, 1;
%e A008302 4 | 1, 3, 5, 6, 5, 3, 1;
%e A008302 5 | 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1;
%e A008302 6 | 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, ...
%e A008302 7 | 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, ...
%e A008302 8 | 1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, ...
%e A008302 9 | 1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, ...
%e A008302 10 | 1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, ...
%e A008302 From _Gus Wiseman_, Aug 12 2020: (Start)
%e A008302 Row n = 4 counts the following submultisets of {1,1,1,2,2,3}:
%e A008302 {} {1} {11} {111} {1112} {11122} {111223}
%e A008302 {2} {12} {112} {1122} {11123}
%e A008302 {3} {22} {122} {1113} {11223}
%e A008302 {13} {113} {1123}
%e A008302 {23} {123} {1223}
%e A008302 {223}
%e A008302 (End)
%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; # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
%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_, Apr 13 2007
%p A008302 # alternative Maple program:
%p A008302 b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
%p A008302 add(b(u+j-1, o-j)*x^(u+j-1), j=1..o)+
%p A008302 add(b(u-j, o+j-1)*x^(u-j), j=1..u)))
%p A008302 end:
%p A008302 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
%p A008302 seq(T(n), n=1..10); # _Alois P. Heinz_, May 02 2017
%t A008302 f[n_] := CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n}], x]; Flatten[Array[f, 8, 0]]
%t A008302 (* Second program: *)
%t A008302 T[0, 0] := 1; T[-1, k_] := 0;
%t A008302 T[n_, k_] := T[n, k] = If[0 <= k <= n*(n - 1)/2, T[n, k - 1] + T[n - 1, k] - T[n - 1, k - n], 0]; (* _Peter Kagey_, Mar 18 2021; corrected the program by _Mats Granvik_ and _Roger L. Bagula_, Jun 19 2011 *)
%t A008302 alternatively (versions 7 and up):
%t A008302 Table[CoefficientList[Series[QFactorial[n,q],{q,0,n(n-1)/2}],q],{n,9}] (* _Wouter Meeussen_, Jul 12 2014 *)
%t A008302 b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,
%t A008302 Sum[b[u + j - 1, o - j]*x^(u + j - 1), {j, 1, o}] +
%t A008302 Sum[b[u - j, o + j - 1]*x^(u - j), {j, 1, u}]]];
%t A008302 T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
%t A008302 Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Apr 21 2025, after _Alois P. Heinz_ *)
%o A008302 (Sage)
%o A008302 from sage.combinat.q_analogues import q_factorial
%o A008302 for n in (1..6): print(q_factorial(n).list()) # _Peter Luschny_, Jul 18 2016
%o A008302 (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 A008302 for(n=1,10, for(k=0,n*(n-1)/2, print1(T(n,k),", ")); print("")) \\ _Paul D. Hanna_, Dec 31 2016
%o A008302 (PARI) row(n)=Vec(prod(k=1,n,(1-'q^k)/(1-'q))); \\ _Joerg Arndt_, Apr 13 2019
%Y A008302 Diagonals: A000707 (k=n-1), A001892 (k=n-2), A001893 (k=n-3), A001894 (k=n-4), A005283 (k=n-5), A005284 (k=n-6), A005285 (k=n-7).
%Y A008302 Columns: A005286 (k=3), A005287 (k=4), A005288 (k=5), A242656 (k=6), A242657 (k=7).
%Y A008302 Rows: A161435 (n=4), A161436 (n=5), A161437 (n=6), A161438 (n=7), A161439 (n=8), A161456 (n=9), A161457 (n=10).
%Y A008302 Row-maxima: A000140, truncated table: A060701, row sums: A000142, row lengths: A000124.
%Y A008302 A001809 gives total Denert index of all permutations.
%Y A008302 A357611 gives a refinement.
%Y A008302 Cf. A000217, A139365, A069777.
%K A008302 easy,tabf,nonn,nice,look
%O A008302 1,5
%A A008302 _N. J. A. Sloane_
%E A008302 There were some mistaken edits to this entry (inclusion of an initial 1, etc.) which I undid. - _N. J. A. Sloane_, Nov 30 2009
%E A008302 Added mention of "major index" to definition. - _N. J. A. Sloane_, Feb 10 2019