A000707 -id:A000707 - cp's OEIS frontend

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.

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, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 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

Offset: 1

N. J. A. Sloane

T(n,k) is the number of permutations of {1..n} with k inversions.
n-th row gives growth series for symmetric group S_n with respect to transpositions (1,2), (2,3), ..., (n-1,n).
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
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
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
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
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).
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
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
Partial sums of rows give triangle A161169. - András Salamon, Feb 16 2013
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
Also series coefficients of q-factorial [n]q ! -- see Mathematica line. - _Wouter Meeussen, Jul 12 2014
From Mikhail Gaichenkov, Aug 16 2016: (Start)
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).
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).
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.
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.
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.
(End)
T(n,k) statistic counts (labeled) permutation graphs with n vertices and k edges. - Mikhail Gaichenkov, Aug 20 2019
From Gus Wiseman, Aug 12 2020: (Start)
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:
  1   2   4   8  24  72 360
      3   6  12  36 120
      5   9  18  40 180
         10  20  60
         15  30  90
             45
Crossrefs:
A336420 is the case with distinct prime multiplicities.
A006939 lists superprimorials or Chernoff numbers.
A022915 counts permutations of prime indices of superprimorials.
A317829 counts factorizations of superprimorials.
A336941 counts divisor chains under superprimorials.
Cf. A000005, A001222, A008278, A022559, A027423, A076954, A181796.
(End)
Named after the British mathematician Percy Alexander MacMahon (1854-1929). - Amiram Eldar, Jun 13 2021
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
Sum_{i>=0} T(n,i)*k^i = A069777(n,k). - Geoffrey Critzer, Feb 26 2025

			1; 1+x; (1+x)*(1+x+x^2) = 1+2*x+2*x^2+x^3; etc.
Triangle begins:
  n\k| 0  1   2    3    4     5     6     7     8      9     10
  ---+--------------------------------------------------------------
   1 | 1;
   2 | 1, 1;
   3 | 1, 2,  2,   1;
   4 | 1, 3,  5,   6,   5,    3,    1;
   5 | 1, 4,  9,  15,  20,   22,   20,   15,    9,     4,     1;
   6 | 1, 5, 14,  29,  49,   71,   90,  101,  101,    90,    71, ...
   7 | 1, 6, 20,  49,  98,  169,  259,  359,  455,   531,   573, ...
   8 | 1, 7, 27,  76, 174,  343,  602,  961, 1415,  1940,  2493, ...
   9 | 1, 8, 35, 111, 285,  628, 1230, 2191, 3606,  5545,  8031, ...
  10 | 1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, ...
From _Gus Wiseman_, Aug 12 2020: (Start)
Row n = 4 counts the following submultisets of {1,1,1,2,2,3}:
  {}  {1}  {11}  {111}  {1112}  {11122}  {111223}
      {2}  {12}  {112}  {1122}  {11123}
      {3}  {22}  {122}  {1113}  {11223}
           {13}  {113}  {1123}
           {23}  {123}  {1223}
                 {223}
(End)

Miklós Bóna, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004 (p. 52).
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.
Florence Nightingale David, Maurice George Kendall, and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 163, top display.
Eugen Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
Valentin V. Petrov, Sums of Independent Random Variables, Springer Berlin Heidelberg, 1975, p. 134.
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Corollary 1.3.10, p. 21.

Alois P. Heinz, Rows n = 1..50, flattened (first 30 rows from Paul D. Hanna)
Ashleigh Adams, Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker, and Amanda Welch, Cyclic sieving on permutations - an analysis of maps and statistics in the FindStat database, arXiv:2402.16251 [math.CO], 2024. See p. 7.
Dorin Andrica and Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics, Vol. 35, No. 1 (2019), pp. 1-11.
Hasan Arslan, A combinatorial interpretation of Mahonian numbers of type B, arXiv:2404.05099 [math.CO], 2024. See p. 3.
E. Ben-Naim, On the Mixing of Diffusing Particles, arXiv:1010.2563 [cond-mat.stat-mech], 2010.
David J. Benson, The cohomology of the nilCoxeter algebra, arXiv:2407.21175 [math.RA], 2024. See p. 4.
Sara C. Billey, Matjaž Konvalinka, and Joshua P. Swanson, Tableaux posets and the fake degrees of coinvariant algebras, arXiv:1809.07386 [math.CO], 2018.
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier, On the Robustness of Winners: Counting Briberies in Elections, arXiv:2010.09678 [cs.GT], 2020.
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, and Stanisław Szufa, Putting a Compass on the Map of Elections, arXiv:2105.07815 [cs.GT], 2021.
J. Bourget, Des permutations, Nouvelles annales de mathématiques, 2e série, tome 10 (1871), pp. 254-268.
Franc Brglez, Of n-dimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction, Elektrotehniski Vestnik, Vol. 78, No. 4 (2011), pp. 181-192.
Agnieszka Bukietyńska, The test of inversion in the analysis of investment funds, Central and Eastern European Journal of Management and Economics, Vol. 5, No. 3 (September 2017), pp. 277-289.
L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math. J., Vol. 15, No. 4 (1948), pp. 987-1000.
Luke Chamandy, Anvar Shukurov, and A. Russ Taylor, Statistical tests of galactic dynamo theory, arXiv:1609.05688 [astro-ph.GA], 2016.
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
Mariusz Czekała and Agnieszka Bukietyńska, Distribution of Inversions and the Power of the τ-Kendall's Test, 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.
Mariusz Czekała, Agnieszka Bukietyńska, and Agnieszka Matylda Schlichtinger, Estimation of the Probability of Inversion in the Test of Variable Dependencies, Information Systems Architecture and Technology: Proceedings of 39th International Conference on Information Systems Architecture and Technology (ISAT 2018), Part III, 145-156.
F. N. David, M. G. Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 241-242. (Annotated scanned copy)
Emeric Deutsch, Problem 10975: Enumeration of Permutations by Disorder, Amer. Math. Monthly, Vol. 111, No. 6 (2004), p. 541.
FindStat - Combinatorial Statistic Finder, The Denert index of a permutation, The major index of a permutation, The number of inversions of a permutation, The sorting index of a permutation.
Dominique Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, in: M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977, pp. 27-49.
Dominique Foata and Doron Zeilberger, Denert's permutation statistic is indeed Euler-Mahonian, Studies in Appl. Math., Vol. 83 (1990), pp. 31-59. [From _Emeric Deutsch_, Oct 29 2008]
Víctor Franco-Sánchez, Arnau Martí-Llobet, and Ramon Ferrer-i-Cancho, Swap distance minimization beyond entropy minimization in word order variation, arXiv:2404.14192 [cs.CL], 2024. See p. 34.
Mikhail Gaichenkov, Necklaces and the generating function for inversions, MathOverflow, 2012.
Mikhail Gaichenkov, Pros and cons of probability model for permutations, MathOverflow, 2014.
Amy Grady, Sorting index and Mahonian-Stirling pairs for labeled forests, Clemson University, July 10, 2014.
Oğuz Gürerk, Ümit Işlak, and Mehmet Akif Yıldız, A study on random permutation graphs, arXiv:1901.06678 [math.CO], 2019.
Richard K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988.
Guo-Niu Han, Une nouvelle bijection pour la statistique de Denert, C. R. Acad. Sci. Paris, Ser. I, Vol. 310 (1990), pp. 493-496.
Stuart A. Hannah, Sieved Enumeration of Interval Orders and Other Fishburn Structures, arXiv:1502.05340 [math.CO], (18-February-2015).
Yang-Hui He, Cyril Matti and Chuang Sun, The Scattering Variety, arXiv preprint arXiv:1403.6833 [hep-th], 2014.
Ekhine Irurozki, Sampling and learning distance-based probability models for permutation spaces, PhD Dissertation, Department of Computer Science and Artificial Intelligence of the University of the Basque Country, 2015.
Ekhine Irurozki, Borja Calvo and José A. Lozano, An R package for permutations, Mallows and Generalized Mallows models, 2014.
Ekhine Irurozki, Borja Calvo and José A. Lozano, PerMallows: An R Package for Mallows and Generalized Mallows Models, Journal of Statistical Software, Vol. 71, No. 12 (August 2016).
Milan Janjic, A Generating Function for Numbers of Insets, Journal of Integer Sequences, Vol. 17 (2014), Article 14.9.7.
Thomas Kahle and Christian Stump, Counting inversions and descents of random elements in finite Coxeter groups, arXiv:1802.01389 [math.CO], 2018-2019.
James A. Koziol, Sums of ranking differences and inversion numbers for method discrimination, Journal of Chemometrics, Vol. 27 (2013), pp. 165-169.
Barbara H. Margolius, Permutations with inversions, J. Integ. Seq., Vol. 4 (2001), Article 01.2.4.
Jeremy L. Martin and Jennifer D. Wagner, On the Spectra of Simplicial Rook Graphs, arXiv preprint arXiv:1209.3493 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 27 2012
Anthony Mendes, A note on alternating permutations, Amer. Math. Monthly, Vol. 114, No. 5 (2007), pp. 437-440.
Vinicus de Morais Alves, Rafael Dowsley, Rafael Timateo de Sousa, and Anderson C.A. Nascimento, Information-Theoretically Secure String Commitments Based on Packet Reordering Channels, IEEE Access, Volume 9 (2021), pp. 139931-139936.
Roger H. Moritz and Robert C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., Vol. 61, No. 1 (1988), pp. 24-29.
Eugen Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.
Eugen Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.
Juan Miguel Nieto, Tailoring and Hexagon Form Factors, Spinning Strings and Correlation Functions in the AdS/CFT Correspondence, Springer Theses (Recognizing Outstanding Ph.D. Research), Springer, Cham, 2018.
Michal Opler, Major index distribution over permutation classes, arXiv:1505.07135 [math.CO], 2015.
Oren Patashnik, Letter to R. H. Moritz & R. C. Williams, cc N. J. A. Sloane, Oct 1988.
Michael Penn, The Quantum Factorial is upon us., YouTube video, 2023.
Nikolay L. Poliakov, Note on level r consensus, arXiv preprint arXiv:1606.04816 [q-fin.EC], 2016.
Svetlana Poznanovic, The sorting index and equidistribution of set-valued statistics over restricted permutations, Journal of Combinatorial Theory, Series A, Vol. 125 (2014), pp. 254-272.
Richard P. Stanley, Binomial posets, Moebius inversion and permutation enumeration, J. Combinat. Theory, Series A, Vol. 20, No. 3 (1976), pp. 336-356.
A. Waksman, On the complexity of inversions, IEEE Trans. Computers, Vol. 19 (1970), pp. 1225-1226. See Table II.
Eric Weisstein's World of Mathematics, Necklace.
Eric Weisstein's World of Mathematics, Irreducible Polynomial.
Thomas Wieder, Comments on A008302.
Wikipedia, Major index

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).
Columns: A005286 (k=3), A005287 (k=4), A005288 (k=5), A242656 (k=6), A242657 (k=7).
Rows: A161435 (n=4), A161436 (n=5), A161437 (n=6), A161438 (n=7), A161439 (n=8), A161456 (n=9), A161457 (n=10).
Row-maxima: A000140, truncated table: A060701, row sums: A000142, row lengths: A000124.
A001809 gives total Denert index of all permutations.
A357611 gives a refinement.
Cf. A000217, A139365, A069777.

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
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
# alternative Maple program:
b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
       add(b(u+j-1, o-j)*x^(u+j-1), j=1..o)+
       add(b(u-j, o+j-1)*x^(u-j), j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=1..10);  # Alois P. Heinz, May 02 2017

f[n_] := CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n}], x]; Flatten[Array[f, 8, 0]]
(* Second program: *)
T[0, 0] := 1; T[-1, k_] := 0;
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 *)
alternatively (versions 7 and up):
Table[CoefficientList[Series[QFactorial[n,q],{q,0,n(n-1)/2}],q],{n,9}] (* Wouter Meeussen, Jul 12 2014 *)
b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,
   Sum[b[u + j - 1, o - j]*x^(u + j - 1), {j, 1, o}] +
   Sum[b[u - j, o + j - 1]*x^(u - j), {j, 1, u}]]];
T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Apr 21 2025, after Alois P. Heinz *)

{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)}
for(n=1,10, for(k=0,n*(n-1)/2, print1(T(n,k),", ")); print("")) \\ Paul D. Hanna, Dec 31 2016

row(n)=Vec(prod(k=1,n,(1-'q^k)/(1-'q))); \\ Joerg Arndt, Apr 13 2019

from sage.combinat.q_analogues import q_factorial
for n in (1..6): print(q_factorial(n).list()) # Peter Luschny, Jul 18 2016

Bourget, Comtet and Moritz-Williams give recurrences.
Mendes and Stanley give g.f.'s.
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.
From Andrew Woods, Sep 26 2012, corrected by Peter Kagey, Mar 18 2021: (Start)
T(1, 0) = 1,
T(n, k) = 0 for n < 0, k < 0 or k > n*(n-1)/2.
T(n, k) = Sum_{j=0..n-1} T(n-1, k-j),
T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n). (End)
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

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

Added mention of "major index" to definition. - N. J. A. Sloane, Feb 10 2019

A008930 Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 21, 41, 80, 157, 310, 614, 1218, 2421, 4819, 9602, 19147, 38204, 76266, 152307, 304256, 607941, 1214970, 2428482, 4854630, 9705518, 19405030, 38800412, 77585314, 155145677, 310251190, 620437691, 1240771141, 2481374234

Offset: 0

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

nonn

a(n) is the number of compositions (p_1,p_2,...) of n with 1<=p_i<=i for all i. a(n) is the number of Dyck n-paths with strictly increasing peaks. To get the correspondence, given such a Dyck path, split the path after the first up step reaching height i, i=1,2,...,h where h is the path's maximum height and count up steps in each block. Example: U-U-DUU-U-DDDD has been split as specified, yielding the composition (1,1,2,1). - David Callan, Feb 18 2004

Row sums of triangle A177517.

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + 21*x^7 + ...
The g.f. equals the following series involving q-factorials:
A(x) = 1 + x + x^2*(1+x) + x^3*(1+x)*(1+x+x^2) + x^4*(1+x)*(1+x+x^2)*(1+x+x^2+x^3) + x^5*(1+x)*(1+x+x^2)*(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4) + ...
From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=21 compositions p(1)+p(2)+...+p(m) = 7 such that p(k) <= k:
  [ 1]  [ 1 1 1 1 1 1 1 ]
  [ 2]  [ 1 1 1 1 1 2 ]
  [ 3]  [ 1 1 1 1 2 1 ]
  [ 4]  [ 1 1 1 1 3 ]
  [ 5]  [ 1 1 1 2 1 1 ]
  [ 6]  [ 1 1 1 2 2 ]
  [ 7]  [ 1 1 1 3 1 ]
  [ 8]  [ 1 1 1 4 ]
  [ 9]  [ 1 1 2 1 1 1 ]
  [10]  [ 1 1 2 1 2 ]
  [11]  [ 1 1 2 2 1 ]
  [12]  [ 1 1 2 3 ]
  [13]  [ 1 1 3 1 1 ]
  [14]  [ 1 1 3 2 ]
  [15]  [ 1 2 1 1 1 1 ]
  [16]  [ 1 2 1 1 2 ]
  [17]  [ 1 2 1 2 1 ]
  [18]  [ 1 2 1 3 ]
  [19]  [ 1 2 2 1 1 ]
  [20]  [ 1 2 2 2 ]
  [21]  [ 1 2 3 1 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3324 (first 201 terms from Vincenzo Librandi)
Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, Subdiagonal and superdiagonal compositions, Art Disc. Appl. Math. (2024). See p. 5.
Roland Bacher, Generic numerical semigroups, hal-03221466 [math.CO], 2021.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.

Cf. A000707, A048285, A177517.

b:= proc(n, i) option remember; `if`(i>=n,
      ceil(2^(n-1)), add(b(n-j, i+1), j=1..min(i, n)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 25 2014, revised Jun 26 2023

Sum[x^n*Product[(1-x^k)/(1-x), {k, 1, n}], {n, 0, 40}]+O[x]^41
Table[SeriesCoefficient[1+Sum[x^j*Product[(1-x^k)/(1-x),{k,1,j}],{j,1,n}],{x,0,n}],{n,0,40}] (* Vaclav Kotesovec, Mar 17 2014 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, i+1], {j, 1, Min[i, n]}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 15 2015, after Alois P. Heinz *)

{ n=8; v=vector(n); for (i=1,n,v[i]=vector(i!)); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, for (a=0,i-1, v[i][j+a*k]=v[i-1][j]+a+1))); c=vector(n); for (i=1,n, for (j=1,i!, if (v[i][j]<=n, c[v[i][j]]++))); c } \\ Jon Perry

N=66; q='q+O('q^N); Vec( sum(n=0,N, q^n * prod(k=1,n, (1-q^k)/(1-q) ) ) ) \\ Joerg Arndt, Mar 24 2014

G.f.: A(x) = Sum_{n>=0} x^n * Product_{k=1..n} (1-x^k)/(1-x). - Paul D. Hanna, Mar 20 2003
G.f.: A(x) = 1/(1 - x/(1+x) /(1 - x/(1+x+x^2) /(1 - x/(1+x+x^2+x^3) /(1 - x/(1+x+x^2+x^3+x^4) /(1 - x/(1+x+x^2+x^3+x^4+x^5) /(1 -...)))))), a continued fraction. - Paul D. Hanna, May 15 2012
Limit_{n->oo} a(n+1)/a(n) = 2. - Mats Granvik, Feb 22 2011
a(n) ~ c * 2^(n-1), where c = 0.288788095086602421... (see constant A048651). - Vaclav Kotesovec, Mar 17 2014

More terms from Paul D. Hanna, Mar 20 2003
Offset corrected to 0 by Joerg Arndt, Mar 24 2014
New name (using comment by David Callan) from Joerg Arndt, Mar 25 2014

A000140 Kendall-Mann numbers: the most common number of inversions in a permutation on n letters is floor(n*(n-1)/4); a(n) is the number of permutations with this many inversions.

Original entry on oeis.org

1, 1, 2, 6, 22, 101, 573, 3836, 29228, 250749, 2409581, 25598186, 296643390, 3727542188, 50626553988, 738680521142, 11501573822788, 190418421447330, 3344822488498265, 62119523114983224, 1214967840930909302, 24965661442811799655, 538134522243713149122

Offset: 1

N. J. A. Sloane

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).
From Ryen Lapham and Anant Godbole, 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 C(n,2), C(n,2)-2,...,2,0,-2,...,-C(n,2), whereas if 4 does not divide n(n-1), A-D may equal C(n,2), C(n,2)-2,...,1,-1,...,-C(n,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((binomial(n,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 and 6.
Define an ordered list to have n terms with terms t(k) for k=1..n. Specify that t(k) ranges from 1 to k, hence the third term t(3) can be 1, 2, or 3. Find all sums of the terms for all n! allowable arrangements to obtain a maximum sum for the greatest number of arrangements. This number is a(n). For n=4, the maximum sum 7 appears in 6 arrangements: 1114, 1123, 1213, 1222, 1231, and 1132. - J. M. Bergot, May 14 2015
Named after the British statistician Maurice George Kendall (1907-1983) and the Austrian-American mathematician Henry Berthold Mann (1905-2000). - Amiram Eldar, Apr 07 2023

			From _Joerg Arndt_, Jan 16 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)
G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 101*x^6 + 573*x^7 + 3836*x^8 + ...

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
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).

Robert Israel, Robert G. Wilson v and N. J. A. Sloane Table of n, a(n) for n = 1..400 (a(1) to a(61) from Sloane, a(62) to a(350) from Wilson).
Dorin Andrica and Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
Dominique Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.
Mikhail Gaichenkov, The property of Kendall-Mann numbers, MathOverflow, 2010.
Richard K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988.
A. Waksman, On the complexity of inversions, IEEE Trans. Computers, 19 (1970), 1225-1226.
Wikipedia, Inversion.
Wikipedia, q-Pochhammer symbol. - _Paul Muljadi_, Jan 18 2011
Index entries for "core" sequences.

Row maxima of A008302.
Odd terms are A186888.
Cf. A000124, A001147, A128566, A181609.

/* based on David W. Wilson's formula */ PS:=PowerSeriesRing(Integers()); [ Max(Coefficients(&*[&+[ x^i: i in [0..j] ]: j in [0..n-1] ])): n in [1..21] ]; // Klaus Brockhaus, Jan 18 2011

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: # James Sellers, Dec 07 2000 [offset is off by 1 - N. J. A. Sloane, May 23 2006]
P:= [1]: a[1]:= 1:
for n from 2 to 100 do
P:= expand(P * add(x^j,j=0..n-1));
a[n]:= max(eval(convert(P,list),x=1));
od:
seq(a[i],i=1..100); # Robert Israel, Dec 14 2014

f[n_] := Max@ CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n-1}], x]; Array[f, 20]
Flatten[{1, 1, Table[Coefficient[Expand[Product[Sum[x^k, {k, 0, m-1}], {m, 1, n}]], x^Floor[n*(n-1)/4]], {n, 3, 20}]}] (* Vaclav Kotesovec, May 13 2016 *)
Table[SeriesCoefficient[QPochhammer[x, x, n]/(1-x)^n, {x, 0, Floor[n*(n-1)/4]}], {n, 1, 20}] (* Vaclav Kotesovec, May 13 2016 *)

{a(n) = if( n<0, 0, vecmax( Vec( prod(k=1, n, 1 - x^k) / (1 - x)^n)))}; /* Michael Somos, Apr 21 2014 */

from math import prod
from sympy import Poly
from sympy.abc import x
def A000140(n): return 1 if n == 1 else max(Poly(prod(sum(x**i for i in range(j+1)) for j in range(n))).all_coeffs()) # Chai Wah Wu, Feb 02 2022

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.
a(n+1)/a(n) = n - 1/2 + O(1/n^{1-epsilon}) as n --> infinity (compare with A008302, A181609, A001147). - Mikhail Gaichenkov, Apr 11 2014
Asymptotics (Mikhail Gaichenkov, 2010): a(n) ~ 6 * n^(n-1) / exp(n). - Vaclav Kotesovec, May 17 2015

Edited by N. J. A. Sloane, Mar 05 2011

A005286 a(n) = (n + 3)(n^2 + 6n + 2)/6.

Original entry on oeis.org

1, 6, 15, 29, 49, 76, 111, 155, 209, 274, 351, 441, 545, 664, 799, 951, 1121, 1310, 1519, 1749, 2001, 2276, 2575, 2899, 3249, 3626, 4031, 4465, 4929, 5424, 5951, 6511, 7105, 7734, 8399, 9101, 9841, 10620, 11439, 12299, 13201, 14146, 15135, 16169, 17249

Offset: 0

N. J. A. Sloane

Number of permutations of [n+3] with three inversions. - Michael Somos, Jun 25 2002
This sequence is related to A241765 by A241765(n) = n*a(n) - Sum_{i=0..n-1} a(i), with A241765(0)=0. For example: A241765(4) = 4*49 - (29+15+6+1) = 145. - Bruno Berselli, Apr 29 2014
For n >= 2, a(n) is also the number of multiplications between two nonzero matrix elements involved in calculating the product of an (n+1) X (n+1) Hessenberg matrix and an (n+1) X (n+1) upper triangular matrix. The formula for n X n matrices is (n+2)(n^2+4n-3)/6 multiplications, n >= 3. - John M. Coffey, Jul 18 2016

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 255, #2, b(n,3).
R. K. Guy, personal communication.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Exercise 1.30, p. 49.

T. D. Noe, Table of n, a(n) for n = 0..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (4, -6, 4, -1).

Cf. A008302, A193106, A193107, A241765.

Table[(n + 3) (n^2 + 6*n + 2)/6, {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 16 2011 *)
LinearRecurrence[{4,-6,4,-1},{1,6,15,29},50] (* Harvey P. Dale, Mar 07 2012 *)
Table[Binomial[n, 3] + Binomial[n, 2] - n, {n, 3, 47}] (* or *)
CoefficientList[Series[(1 + 2 x - 3 x^2 + x^3)/(1 - x)^4, {x, 0, 44}], x] (* Michael De Vlieger, Jul 09 2016 *)

a(n)=n+=3; (n^3-7*n)/6 /* Michael Somos, May 12 2005 */

G.f.: (1+2*x-3*x^2+x^3)/(1-x)^4. - Simon Plouffe in his 1992 dissertation
a(-6-n) = -a(n). - Michael Somos, May 12 2005
a(n) = a(n-1) + A000096(n+1) = A005581(n+2) - 1. - Henry Bottomley, Oct 25 2001
(m^3-7*m)/6 for m >= 3 gives the same sequence. - N. J. A. Sloane, Jul 15 2011
a(0)=1, a(1)=6, a(2)=15, a(3)=29, a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Harvey P. Dale, Mar 07 2012
E.g.f.: (6 + 30*x + 12*x^2 + x^3)*exp(x)/6. - Ilya Gutkovskiy, Jul 09 2016

A001892 Number of permutations of (1,...,n) having n-2 inversions (n>=2).

Original entry on oeis.org

1, 2, 5, 15, 49, 169, 602, 2191, 8095, 30239, 113906, 431886, 1646177, 6301715, 24210652, 93299841, 360490592, 1396030396, 5417028610, 21056764914, 81978913225, 319610939055, 1247641114021, 4875896455975, 19075294462185, 74696636715792, 292758662041150

Offset: 2

N. J. A. Sloane, R. K. Guy

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(4)=5  because we have 1342, 1423, 2143, 2314, and 3124.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
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).

G. C. Greubel, Table of n, a(n) for n = 2..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
E. Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.

Cf. A008302, A048651.

f := (x,n)->product((1-x^j)/(1-x),j=1..n); seq(coeff(series(f(x,n),x,n+2),x,n-2), n=2..40);

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-2}],{n,2,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-3)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.288788095... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, Maple code, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

A001893 Number of permutations of (1,...,n) having n-3 inversions (n>=3).

Original entry on oeis.org

1, 3, 9, 29, 98, 343, 1230, 4489, 16599, 61997, 233389, 884170, 3366951, 12876702, 49424984, 190297064, 734644291, 2842707951, 11022366544, 42815701060, 166583279325, 649063995030, 2532267577126, 9891097066760, 38676401680776, 151381995733542, 593053313030007

Offset: 3

N. J. A. Sloane

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(4)=3  because we have 1243, 1324, and 2134.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
R. K. Guy, personal communication.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 15.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
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).

G. C. Greubel, Table of n, a(n) for n = 3..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
E. Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.

Cf. A008302, A048651.

f := (x,n)->product((1-x^j)/(1-x),j=1..n); seq(coeff(series(f(x,n),x,n+2),x,n-3), n=3..40); # Barbara Haas Margolius, May 31 2001

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-3}],{n,3,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-4)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

A001894 Number of permutations of {1,...,n} having n-4 inversions (n>=4).

Original entry on oeis.org

1, 4, 14, 49, 174, 628, 2298, 8504, 31758, 119483, 452284, 1720774, 6574987, 25214332, 96997223, 374153699, 1446677555, 5605337934, 21758936146, 84604366100, 329453055975, 1284626463105, 5015200610785, 19601107218591, 76685359017750, 300294650988857, 1176939165980809

Offset: 4

N. J. A. Sloane

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(5)=4  because we have 21345, 13245, 12435, and 12354.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
R. K. Guy, personal communication.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
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).

G. C. Greubel, Table of n, a(n) for n = 4..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
E. Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.

Cf. A008302, A048651.

f := (x,n)->product((1-x^j)/(1-x),j=1..n); seq(coeff(series(f(x,n),x,n+2),x,n-4), n=4..40); # Barbara Haas Margolius, May 31 2001

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-4}],{n,4,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-5)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

A005283 Number of permutations of (1,...,n) having n-5 inversions (n>=5).

Original entry on oeis.org

1, 5, 20, 76, 285, 1068, 4015, 15159, 57486, 218895, 836604, 3208036, 12337630, 47572239, 183856635, 712033264, 2762629983, 10736569602, 41788665040, 162869776650, 635562468075, 2482933033659, 9710010151831, 38008957336974, 148912655255315, 583885852950802

Offset: 5

N. J. A. Sloane

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(6)=5 because we have 213456, 132456, 124356, 123546, and 123465.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
R. K. Guy, personal communication.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 5..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.

Cf. A008302, A000707, A001892, A001893, A001894, A005284, A005285, A048651.

f := (x,n)->product((1-x^j)/(1-x),j=1..n); seq(coeff(series(f(x,n),x,n+2),x,n-5), n=5..40); # Barbara Haas Margolius, May 31 2001

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-5}],{n,5,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-6)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

A005284 Number of permutations of (1,...,n) having n-6 inversions (n>=6).

Original entry on oeis.org

1, 6, 27, 111, 440, 1717, 6655, 25728, 99412, 384320, 1487262, 5762643, 22357907, 86859412, 337879565, 1315952428, 5131231668, 20029728894, 78265410550, 306109412100, 1198306570554, 4694809541046, 18407850118383

Offset: 6

N. J. A. Sloane

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(7)=6 because we have 2134567, 1324567, 1243567, 1235467, 1234657 and 1234576.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
R. K. Guy, personal communication.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 6..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.

Cf. A008302, A000707, A001892, A001893, A001894, A005283, A005285, A048651.

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; seq(g(j+6,j),j=0..30); # Barbara Haas Margolius, May 31 2001

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-6}],{n,6,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-7)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

A005285 Number of permutations of (1,...,n) having n-7 inversions (n>=7).

Original entry on oeis.org

1, 7, 35, 155, 649, 2640, 10569, 41926, 165425, 650658, 2554607, 10020277, 39287173, 154022930, 603919164, 2368601685, 9293159292, 36476745510, 143239635450, 562744102479, 2211876507387, 8697839966552, 34218338900591

Offset: 7

N. J. A. Sloane

nonn

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

			a(8)=7 because we have 21345678, 13245678, 12435678, 12354678, 12346578, 12345768, and 12345687.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
R. K. Guy, personal communication.
E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 7..1000
R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.

Cf. A008302, A000707, A001892, A001893, A001894, A005283, A005284, A048651.

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; seq(g(j+7,j),j=0..30); # Barbara Haas Margolius, May 31 2001

Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-7}],{n,7,25}] (* Vaclav Kotesovec, Mar 16 2014 *)

a(n) = 2^(2*n-8)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014

More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001

Definition clarified by Emeric Deutsch, Aug 02 2014

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A008930 Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A000140 Kendall-Mann numbers: the most common number of inversions in a permutation on n letters is floor(n*(n-1)/4); a(n) is the number of permutations with this many inversions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A005286 a(n) = (n + 3)*(n^2 + 6*n + 2)/6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A001892 Number of permutations of (1,...,n) having n-2 inversions (n>=2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A001893 Number of permutations of (1,...,n) having n-3 inversions (n>=3).

Views

Author

Keywords

A005286 a(n) = (n + 3)(n^2 + 6n + 2)/6.