A008278 -id:A008278 - cp's OEIS frontend

A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1 <= k <= n.

1, -1, 1, 2, -3, 1, -6, 11, -6, 1, 24, -50, 35, -10, 1, -120, 274, -225, 85, -15, 1, 720, -1764, 1624, -735, 175, -21, 1, -5040, 13068, -13132, 6769, -1960, 322, -28, 1, 40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1, -362880, 1026576, -1172700, 723680, -269325, 63273, -9450, 870, -45, 1

Offset: 1

N. J. A. Sloane

The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.
The unsigned numbers (read from right to left) also give the number of permutations of 1..n with complexity k, where the complexity of a permutation is defined to be the sum of the lengths of the cycles minus the number of cycles. In other words, the complexity equals the sum of (length of cycle)-1 over all cycles. For n=5, the numbers of permutations with complexity 0,1,2,3,4 are 1, 10, 35, 50, 24. - N. J. A. Sloane, Feb 08 2019
The unsigned numbers are also the number of permutations of 1..n with k left to right maxima (see Khovanova and Lewis, Smith).
With P(n) = the number of integer partitions of n, T(i,n) = the number of parts of the i-th partition of n, D(i,n) = the number of different parts of the i-th partition of n, p(j,i,n) = the j-th part of the i-th partition of n, m(j,i,n) = multiplicity of the j-th part of the i-th partition of n, Sum_[T(i,n)=k]{i=1}^{P(n)} = sum running from i=1 to i=p(n) but taking only partitions with T(i,n)=k parts into account, Product{j=1..T(i,n)} = product running from j=1 to j=T(i,n), Product_{j=1..D(i,n)} = product running from j=1 to j=D(i,n) one has S1(n,k) = Sum_[T(i,n)=k]{i=1}^{P(n)} (n!/Product{j=1..T(i,n)} p(j,i,n))* (1/Product_{j=1..D(i,n)} m(j,i,n)!). For example, S1(6,3) = 225 because n=6 has the following partitions with k=3 parts: (114), (123), (222). Their complexions are: (114): (6!/1*1*4)*(1/2!*1!) = 90, (123): (6!/1*2*3)*(1/1!*1!*1!) = 120, (222): (6!/2*2*2)*(1/3!) = 15. The sum of the complexions is 90+120+15 = 225 = S1(6,3). - Thomas Wieder, Aug 04 2005
Row sums equal 0. - Jon Perry, Nov 14 2005
|s(n,k)| enumerates unordered n-vertex forests composed of k increasing non-plane (unordered) trees. Proof from the e.g.f. of the first column and the F. Bergeron et al. reference, especially Table 1, last row (non-plane "recursive"), given in A049029. - Wolfdieter Lang, Oct 12 2007
|s(n,k)| enumerates unordered increasing n-vertex k-forests composed of k unary trees (out-degree r from {0,1}) whose vertices of depth (distance from the root) j >= 0 come in j+1 colors (j=0 for the k roots). - Wolfdieter Lang, Oct 12 2007, Feb 22 2008
A refinement of the unsigned array is A036039. For an association to forests of "naturally grown" rooted non-planar trees, dispositions of flags on flagpoles, and colorings of the vertices of the complete graphs K_n, see A130534. - Tom Copeland, Mar 30 and Apr 05 2014
The Stirling numbers of the first kind were related to the falling factorial and the convolved, or generalized, Bernoulli numbers B_n by Norlund in 1924 through Sum_{k=1..n+1} T(n+1,k) * x^(k-1) = (x-1)!/(x-1-n)! = (x + B.(0))^n = B_n(x), umbrally evaluated with (B.(0))^k = B_k(0) and the associated Appell polynomial B_n(x) defined by the e.g.f. (t/(exp(t) - 1))^(n+1) * exp(x*t) = exp(B.(x)t). - Tom Copeland, Sep 29 2015
With x = e^z, D_x = d/dx, D_z = d/dz, and p_n(x) the row polynomials of this entry, x^n (D_x)^n = p_n(D_z) = (D_z)! / (D_z - n)! = (xD_x)! / (xD_x - n)!. - Tom Copeland, Nov 27 2015
From the operator relation z + Psi(1) + sum_{n > 0} (-1)^n (-1/n) binomial(D,n) = z + Psi(1+D) with D = d/dz and Psi the digamma function, Zeta(n+1) = Sum_{k > n-1} (1/k) |S(k,n)| / k! for n > 0 and Zeta the Riemann zeta function. - Tom Copeland, Aug 12 2016
Let X_1,...,X_n be i.i.d. random variables with exponential distribution having mean = 1.  Let Y = max{X_1,...,X_n}.  Then (-1)^n*n!/( Sum_{k=1..n+1} a(n+1,k) t^(k-1) ) is the moment generating function of Y.  The expectation of Y is the n-th harmonic number. - Geoffrey Critzer, Dec 25 2018
In the Ewens sampling theory describing the multivariate probability distribution of the sizes of the allelic classes in a sample of size n under the Infinite Alleles Model, |s(n,k)| gives the coefficient in the formula for the probability that a sample of n alleles has exactly k distinct types. - Noah A Rosenberg, Feb 10 2019
Named by Nielson (1906) after the Scottish mathematician James Stirling (1692-1770). - Amiram Eldar, Jun 11 2021 and Oct 02 2023
The first few row polynomials along with a recursion formula are found in a manuscript by Newton written in 1664 or 1665 (p. 169 of Turnbull) giving a geometric presentation of the binomial theorem for rational powers. - Tom Copeland, Dec 10 2022

			|s(3,2)| = 3 for the three unordered 2-forest with 3 vertices and two increasing (nonplane) trees: ((1),(2,3)), ((2),(1,3)), ((3),(1,2)).
Triangle begins:
                                      1
                                 -1,      1
                               2,    -3,      1
                          -6,    11,     -6,     1
                      24,    -50,    35,    -10,    1
                -120,    274,  -225,     85,   -15,    1
             720,  -1764,   1624,  -735,    175,  -21,   1
       -5040,  13068, -13132,  6769,  -1960,   322,  -28,  1
  40320, -109584, 118124, -67284, 22449,  -4536,  546, -36,  1
Another version of the same triangle, from _Joerg Arndt_, Oct 05 2009: (Start)
s(n,k) := number of permutations of n elements with exactly k cycles ("Stirling cycle numbers")
  n|  total   m=1      2      3     4     5    6   7  8 9
  -+-----------------------------------------------------
  1|      1     1
  2|      2     1      1
  3|      6     2      3      1
  4|     24     6     11      6     1
  5|    120    24     50     35    10     1
  6|    720   120    274    225    85    15    1
  7|   5040   720   1764   1624   735   175   21   1
  8|  40320  5040  13068  13132  6769  1960  322  28  1
  9| 362880 40320 109584 118124 67284 22449 4536 546 36 1
(End)
|s(4,2)| = 11 for the eleven unordered 2-forest with 4 vertices, composed of two increasing (nonplane) trees: ((1),((23)(24))), ((2),((13)(14))), ((3),((12)(14))), ((4),((12)(13))); ((1),(2,3,4)),((2),(1,2,3)), ((3), (1,2,4)), ((4),(1,2,3)); ((1,2),(3,4)), ((1,3),(2,4)), ((1,4),(2,3)). - _Wolfdieter Lang_, Feb 22 2008

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.
Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 93ff.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
George Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
Louis Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.
John H. Conway and Richard K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 93.
Florence Nightingale David, Maurice George Kendall and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.
Saber N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
Herman H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245. In the second edition, see Chapter 6, especially p. 259.
M. Miyata and J. W. Son, On the complexity of permutations and the metric space of bijections, Tensor, 60 (1998), No. 1, 109-116 (MR1768839).
Isaac Newton, A Method whereby to find ye areas of Those Lines wch can be squared, pp. 168-171 of Turnbull below.
John Riordan, An Introduction to Combinatorial Analysis, p. 48.
Robert Sedgewick and Phillipe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
H. Turnbull (editor), The Correspondence of Isaac Newton Vol. II 1676-1687, Cambridge Univ. Press, 1960.

T. D. Noe, Rows 1 to 100 of triangle, flattened.
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv:1111.3061 [math.PR], 2011.
Joerg Arndt, Matters Computational (The Fxtbook), p. 277.
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
Elena Barcucci, Alberto Del Lungo and Renzo Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, Vol. 159 (1996), pp. 29-42.
Nicolas Behr, Vincent Danos, and Ilias Garnier, Combinatorial Conversion and Moment Bisimulation for Stochastic Rewriting Systems, arXiv:1904.07313 [cs.LO], 2019.
Hacene Belbachir and Mourad Rahmani, Alternating Sums of the Reciprocals of Binomial Coefficients, Journal of Integer Sequences, Vol. 15 (2012), Article 12.2.8.
Edward A. Bender, Central and local limit theorems applied to asymptotic enumeration Journal of Combinatorial Theory, Series A, Vol. 15, No. 1 (1973), pp. 91-111. See Example 5.1.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 32.
Federico Castillo, Damian de la Fuente, Nicolas Libedinsky, and David Plaza, On the size of Bruhat intervals, arXiv:2309.08539 [math.CO], 2023.
José Luis Cereceda,, Generalized Akiyama-Tanigawa Algorithm for Hypersums of Powers of Integers, J. Int. Seq., Vol. 16 (2013), Article 13.3.2.
José Luis Cereceda, Iterative Procedure for Hypersums of Powers of Integers, Journal of Integer Sequences, Vol. 17 (2014), Article 14.5.3.
Ricky X. F. Chen, A Note on the Generating Function for the Stirling Numbers of the First Kind, Journal of Integer Sequences, Vol. 18 (2015), Article 15.3.8.
Tom Copeland, A Class of Differential Operators and the Stirling Numbers, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, Lagrange a la Lah.
Harry Crane, The ubiquitous Ewens sampling formula, Statistical Science, Vol. 31 (2016), pp. 1-19.
Thierry Dana-Picard and David G. Zeitoun, Sequences of definite integrals, infinite series and Stirling numbers, International Journal of Mathematical Education in Science and Technology, Vol. 43, No. 2 (2012), pp. 219-230.
Sajal K. Das, Joydeep Ghosh and Narsingh Deo, Stirling networks: a versatile combinatorial topology for multiprocessor systems, Discrete Applied Mathematics, Vol. 37 (1992), pp. 119-146.
Robert M. Dickau, Stirling numbers of the first kind.
Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, Vol. 22, No. 4 (2015), #P4.10.
B. S. El-Desouky, Nenad P. Cakić and Toufik Mansour, Modified approach to generalized Stirling numbers via differential operators, Appl. Math. Lett., Vol. 23, No. 1 (2010), pp. 115-120.
FindStat - Combinatorial Statistic Finder, The number of saliances of a permutation, The number of cycles in the cycle decomposition of a permutation.
Bill Gosper, Colored illustrations of triangle of Stirling numbers of first kind read mod 2, 3, 4, 5, 6, 7.
Daniel B. Grünberg, On asymptotics, Stirling numbers, gamma function and polylogs, Results in Mathematics, Vol. 49, No. 1 (2006), pp. 89-125; arXiv preprint, arXiv:math/0607514 [math.CO], 2006.
Jerome Hines, A generalization of the S-Stirling numbers, Math. Mag., Vol. 29, No. 4 (1956), pp. 200-203.
Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa Matrix, Journal of Integer Sequences, 8 (2005), Article 05.2.7.
Charles Knessl and Joseph B. Keller, Stirling number asymptotics from recursion equations using the ray method, Stud. Appl. Math., Vol. 84, No. 1 (1991), pp. 43-56.
Tanya Khovanova and Joel Brewster Lewis, Skyscrapers.
Donald E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA], 1993; The Mathematica J., 2 (1992), 67-78.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), Article 00.2.4.
Elliott H. Lieb, Concavity properties and a generating function for Stirling numbers, Journal of Combinatorial Theory, Vol. 5, No. 2 (1968), pp. 203-206.
Daniel E. Loeb, A generalization of Stirling numbers, arXiv:math/9502217 [math.CO], 1995.
Mahid M. Mangontarum and Jacob Katriel, On q-Boson Operators and q-Analogues of the r-Whitney and r-Dowling Numbers, J. Int. Seq., Vol. 18 (2015), Article 15.9.8.
Toufik Mansour, Augustine Munagi and Mark Shattuck, Recurrence Relations and Two-Dimensional Set Partitions, J. Int. Seq., Vol. 14 (2011), Article 11.4.1.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.3.
B. H. Margolius, Transient and periodic solution to the time-inhomogeneous quasi-birth death process, Queueing Systems, Volume 56, Numbers 3-4 / August, 2007. [From _N. J. A. Sloane_, Jul 09 2009]
Dragoslav S. Mitrinović, Sur une relation de récurrence relative aux nombres de Bernoulli, Comptes rendus de l'Académie des sciences de Paris, Vol. 250 (1960), pp. 4266-4267.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Sur les nombres de Stirling et les nombres de Bernoulli d'ordre supérieur, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 43 (1960), pp. 1-63.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Sur une classe de nombres se rattachant aux nombres de Stirling--Appendice: Table des nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 60 (1961), pp. 1-15 and 17-62.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Tableaux d'une classe de nombres reliés aux nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 77 (1962), pp. 1-77.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Tableaux d'une classe de nombres reliés aux nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 77 (1962), pp. 1-77 [jstor stable version].
Emanuele Munarini, Combinatorial identities involving the central coefficients of a Sheffer matrix, Applicable Analysis and Discrete Mathematics, Vol. 13 (2019), pp. 495-517.
Niels Nielson, Handbuch der theorie der gammafunktion, Teubner, Leipzig, 1906, see p. 67.
Niels Nörlund, Vorlesungen über Differenzenrechnung, Springer, Berlin, 1924.
Niels Nörlund, Vorlesungen über Differenzenrechnung, Chelsea Pub. Co., New York, 1954. [archive.org]
K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. Vol. 50 (2009), 083512.
Grzegorz Rządkowski, Two formulas for Successive Derivatives and Their Applications, J. Int. Seq., Vol. 12 (2009), Article 09.8.2.
Maxie D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications, J. Int. Seq., Vol. 13 (2010), Article 10.6.7.
Benjamin Schreyer, Rigged Horse Numbers and their Modular Periodicity, arXiv:2409.03799 [math.CO], 2024. See p. 12.
Raymond Scurr and Gloria Olive, Stirling numbers revisited, Discrete Math., Vol. 189, No. 1-3 (1998), pp. 209-219. MR1637761 (99d:11019).
Mark Shattuck, Convolution identities for Stirling numbers of the first kind via involution, INTEGERS, Vol. 12 (2012), #A59. - From _N. J. A. Sloane_, Feb 04 2013
Mark Shattuck, Combinatorial Proofs of Some Stirling Number Convolution Formulas, J. Int. Seq., Vol. 25 (2022), Article 22.2.2.
Warren D. Smith, Puzzle: Counting new records.
Michael Z. Spivey, A generalized recurrence for Bell Numbers, JIS, Vol. 11 (2008), Article 08.2.5.
Michael Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq., Vol. 14 (2011), Article 11.9.7.
Richard P. Stanley, Ordering events in Minkowski space, arXiv:math/0501256 [math.CO], 2005.
James Stirling, The Differential Method, London, 1749; see p. 10.
Nico M. Temme, Asymptotic Estimates of Stirling Numbers, Studies in Applied Mathematics, Vol. 89, No. 3 (1993), pp. 233-243; Summary by Helmut Prodinger.
A. N. Timashev, On asymptotic expansions of Stirling numbers of the first and second kinds, (Russian) Diskret. Mat. 10(3) (1998), 148-159; translation in Discrete Math. Appl., Vol. 8, No. 5 (1998), pp. 533-544.
Eric Weisstein's World of Mathematics, Permutation Cycle.
Eric Weisstein's World of Mathematics, Stirling Number of the First Kind.
Thomas Wieder, Comments on A008275.
OEIS Wiki, Factorial polynomials.
Index entries for "core" sequences

Diagonals: A000217, A000914, A001303, A000915, A053567, etc.
Cf. A048994, A008277 (Stirling numbers of second kind), A039814, A039815, A039816, A039817, A048993, A087748.
Cf. A084938, A094216, A008276 (row reversed), A008277, A008278, A094262, A121632, A130534 (unsigned version), A087755 (triangle mod 2), A000142 (row sums of absolute values).

a008275 n k = a008275_tabl !! (n-1) !! (k-1)
a008275_row n = a008275_tabl !! (n-1)
a008275_tabl = map tail $ tail a048994_tabl
-- Reinhard Zumkeller, Mar 18 2013

with (combinat):seq(seq(stirling1(n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 03 2007
for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; # Zerinvary Lajos, Nov 29 2007

Flatten[Table[StirlingS1[n, k], {n, 1, 10}, {k, 1, n}]] (* Jean-François Alcover, May 18 2011 *)
Flatten@Table[Coefficient[Product[x-k, {k, 0, n-1}], x, Range[n]], {n, Range[10]}] (* Oliver Seipel, Jun 11 2024 *)
a[n_, n_] := 1; a[n_, 0] := 0; a[0, k_] := 0;
a[n_, k_] := a[n, k] = a[n-1, k-1] + (n-1) a[n-1, k];
Flatten@Table[(-1)^(n-k) a[n, k], {n, 1, 10}, {k, 1, n}] (* Oliver Seipel, Jun 11 2024 *)

create_list(stirling1(n+1,k+1),n,0,30,k,0,n); /* Emanuele Munarini, Jun 01 2012 */

T(n,k)=if(n<1,0,n!*polcoeff(binomial(x,n),k))

T(n,k)=if(n<1,0,n!*polcoeff(polcoeff((1+x+x*O(x^n))^y,n),k))

vecstirling(n)=Vec(factorback(vector(n-1,i,1-i*'x))) /* (A function that returns all the s(n,k) as a vector) */ \\ Bill Allombert (Bill.Allombert(AT)math.u-bordeaux1.fr), Mar 16 2009

s(n, k) = s(n-1, k-1) - (n-1)*s(n-1, k), n, k >= 1; s(n, 0) = s(0, k) = 0; s(0, 0) = 1.
The unsigned numbers a(n, k)=|s(n, k)| satisfy a(n, k) = a(n-1, k-1) + (n-1)*a(n-1, k), n, k >= 1; a(n, 0) = a(0, k) = 0; a(0, 0) = 1.
E.g.f.: for m-th column (unsigned): ((-log(1-x))^m)/m!.
s(n, k) = T(n-1, k-1), n>1 and k>1, where T(n, k) is the triangle [ -1, -1, -2, -2, -3, -3, -4, -4, -5, -5, -6, -6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, ...] and DELTA is Deléham's operator defined in A084938. The unsigned numbers are also |s(n, k)| = T(n-1, k-1), for n>0 and k>0, where T(n, k) = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...].
Sum_{i=0..n} (-1)^(n-i) * StirlingS1(n, i) * binomial(i, k) = (-1)^(n-k) *  StirlingS1(n+1, k+1). - Carlo Wood (carlo(AT)alinoe.com), Feb 13 2007
G.f. for row n: Product_{j=1..n} (x-j) (e.g., (x-1)*(x-2)*(x-3) = x^3 - 6*x^2 + 11*x - 6). - Jon Perry, Nov 14 2005
s(n,k) = A048994(n,k), for k=1..n. - Reinhard Zumkeller, Mar 18 2013 (Corrected by N. J. A. Sloane, May 07 2025 at the suggestion of Manfred Boergens, May 07 2025)
As lower triangular matrices A008277*A008275 = I, the identity matrix. - Tom Copeland, Apr 25 2014
a(n,k) = s(n,k) = lim_{y -> 0} Sum_{j=0..k} (-1)^j*binomial(k,j)*((-j*y)!/(-j*y-n)!)*y^(-k)/k! = Sum_{j=0..k} (-1)^(n-j)*binomial(k,j)*((j*y - 1 + n)!/(j*y-1)!)*y^(-k)/k!. - Tom Copeland, Aug 28 2015
From Daniel Forgues Jan 16 2016: (Start)
Let x_(0) := 1 (empty product), and for n >= 1:
  x_(n) := Product_{k=0..n-1} (x-k), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), and also x_(-n) := 1 / [Product_{k=0..n-1} (x+k)].
Then, for n >= 1: x_(n) = Sum_{k=1..n} T(n,k) * x^k, 1 / [x_(-n)] = Sum_{k=1..n} |T(n,k)| * x^k, x^n = Sum_{k=1..n} A008277(n,k) * x_(k), where A008277(n,k) are Stirling numbers of the second kind.
The row sums (of either signed or absolute values) are Sum_{k=1..n} T(n,k) = 0^(n-1), Sum_{k=1..n} |T(n,k)| = T(n+1,1) = n!. (End)
s(n,m) = ((-1)^(n-m)/n)*Sum_{i=0..m-1} C(2*n-m-i, m-i-1)*A008517(n-m+1,n-m-i+1). - Vladimir Kruchinin, Feb 14 2018
Orthogonal relation: Sum_{i=0..n} i^p*Sum_{j=k..n} (-1)^(i+j) * binomial(j,i) * Stirling1(j,k)/j! = delta(p,k), i,k,p <= n, n >= 1. - Leonid Bedratyuk, Jul 27 2020
From Zizheng Fang, Dec 28 2020: (Start)
Sum_{k=1..n} (-1)^k * k * T(n, k) = -T(n+1, 2).
Sum_{k=1..n} k * T(n, k) = (-1)^n * (n-2)! = T(n-1, 1) for n>=2. (End)
n-th row polynomial = n!*Sum_{k = 0..2*n} (-1)^(n+k)*binomial(x, k)*binomial(x-1, 2*n-k) = n!*Sum_{k = 0..2*n+1} (-1)^(n+k+1)*binomial(x, k)*binomial(x-1, 2*n+1-k). - Peter Bala, Mar 29 2024

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.

Original entry on oeis.org

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

A336420 Irregular triangle read by rows where T(n,k) is the number of divisors of the n-th superprimorial A006939(n) with distinct prime multiplicities and k prime factors counted with multiplicity.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 5, 2, 1, 1, 1, 4, 3, 11, 7, 7, 10, 5, 2, 1, 1, 1, 5, 4, 19, 14, 18, 37, 25, 23, 15, 23, 10, 5, 2, 1, 1, 1, 6, 5, 29, 23, 33, 87, 70, 78, 74, 129, 84, 81, 49, 39, 47, 23, 10, 5, 2, 1, 1, 1, 7, 6, 41, 34, 52, 165, 144, 183, 196, 424, 317, 376, 325, 299, 431, 304, 261, 172, 129, 81, 103, 47, 23, 10, 5, 2, 1, 1

Offset: 0

Gus Wiseman, Jul 25 2020

A number's prime signature (row n of A124010) is the sequence of positive exponents in its prime factorization, so a number has distinct prime multiplicities iff all the exponents in its prime signature are distinct.
The n-th superprimorial or Chernoff number is A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1).
T(n,k) is also the number of length-n vectors 0 <= v_i <= i summing to k whose nonzero values are all distinct.

			Triangle begins:
  1
  1  1
  1  2  1  1
  1  3  2  5  2  1  1
  1  4  3 11  7  7 10  5  2  1  1
  1  5  4 19 14 18 37 25 23 15 23 10  5  2  1  1
The divisors counted in row n = 4 are:
  1  2  4     8   16   48   144   432  2160  10800  75600
     3  9    12   24   72   360   720  3024
     5  25   18   40   80   400  1008
     7       20   54  108   504  1200
             27   56  112   540  2800
             28  135  200   600
             45  189  675   756
             50            1350
             63            1400
             75            4725
            175

A000110 gives row sums.
A000124 gives row lengths.
A000142 counts divisors of superprimorials.
A006939 lists superprimorials or Chernoff numbers.
A008278 is the version counting only distinct prime factors.
A008302 counts divisors of superprimorials by bigomega.
A022915 counts permutations of prime indices of superprimorials.
A076954 can be used instead of A006939.
A130091 lists numbers with distinct prime multiplicities.
A146291 counts divisors by bigomega.
A181796 counts divisors with distinct prime multiplicities.
A181818 gives products of superprimorials.
A317829 counts factorizations of superprimorials.
A336417 counts perfect-power divisors of superprimorials.
A336498 counts divisors of factorials by bigomega.
A336499 uses factorials instead superprimorials.
Cf. A000005, A001222, A008278, A027423, A071625, A124010, A327498, A336419, A336421, A336426, A336500, A336568.

chern[n_]:=Product[Prime[i]^(n-i+1),{i,n}];
Table[Length[Select[Divisors[chern[n]],PrimeOmega[#]==k&&UnsameQ@@Last/@FactorInteger[#]&]],{n,0,5},{k,0,n*(n+1)/2}]

A336419 Number of divisors d of the n-th superprimorial A006939(n) with distinct prime exponents such that the quotient A006939(n)/d also has distinct prime exponents.

Original entry on oeis.org

1, 2, 4, 10, 24, 64, 184, 536, 1608, 5104, 16448, 55136, 187136, 658624, 2339648, 8618208, 31884640, 121733120, 468209408, 1849540416, 7342849216

Offset: 0

Gus Wiseman, Jul 25 2020

A number has distinct prime exponents iff its prime signature is strict.

The n-th superprimorial or Chernoff number is A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1).

			The a(0) = 1 through a(3) = 10 divisors:
  1  2  12  360
-----------------
  1  1   1    1
     2   3    5
         4    8
        12    9
             18
             20
             40
             45
             72
            360

A000110 shifted once to the left dominates this sequence.
A006939 lists superprimorials or Chernoff numbers.
A022915 counts permutations of prime indices of superprimorials.
A130091 lists numbers with distinct prime exponents.
A181796 counts divisors with distinct prime exponents.
A181818 gives products of superprimorials.
A317829 counts factorizations of superprimorials.
A336417 counts perfect-power divisors of superprimorials.
Cf. A000005, A000178, A008278, A071625, A076954, A118914, A124010, A327498, A327527, A336420, A336421, A336426, A336500, A336568.

chern[n_]:=Product[Prime[i]^(n-i+1),{i,n}];
Table[Length[Select[Divisors[chern[n]],UnsameQ@@Last/@FactorInteger[#]&&UnsameQ@@Last/@FactorInteger[chern[n]/#]&]],{n,0,6}]

recurse(n,k,b,d)={if(k>n, 1, sum(i=0, k, if((i==0||!bittest(b,i)) && (i==k||!bittest(d,k-i)), self()(n, k+1, bitor(b, 1<Andrew Howroyd, Aug 30 2020

a(10)-a(20) from Andrew Howroyd, Aug 31 2020

A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 1, 11, 25, 15, 1, 26, 130, 210, 105, 1, 57, 546, 1750, 2205, 945, 1, 120, 2037, 11368, 26775, 27720, 10395, 1, 247, 7071, 63805, 247555, 460845, 405405, 135135, 1, 502, 23436, 325930, 1939630, 5735730, 8828820, 6756750, 2027025, 1

Offset: 0

Wolfdieter Lang, Oct 14 2005

Previous name was: Coefficient triangle of polynomials used for e.g.f.s of Stirling2 diagonals.
For the o.g.f. of diagonal k of the Stirling2 triangle one has a similar result. See A008517 (second-order Eulerian triangle).
A(m,x), the o.g.f. for column m, satisfies the recurrence A(m,x) = x*(x*(d/dx)A(m-1,x) + m*A(m-1,x))/(1-(m+1)*x), for m >= 1 and A(0,x) = 1/(1-x).
The e.g.f. for the sequence in column k+1, k >= 0, of A008278, i.e., for the diagonal k >= 0 of the Stirling2 triangle A048993, is exp(x)*Sum_{m=0..k} a(k,m)*(x^(m+k))/(m+k)!.
It appears that the triangles in this sequence and A124324 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
A refined version of this triangle is given in A356145, which contains a link providing the precise relationship between A124324 and this entry, confirming Jörgen Backelin's observation above. - Tom Copeland, Sep 24 2022

			Triangle starts:
  [1]
  [1, 1]
  [1, 4,  3]
  [1, 11, 25,  15]
  [1, 26, 130, 210,  105]
  [1, 57, 546, 1750, 2205, 945]
  ...
The e.g.f. of [0,0,1,7,25,65,...], the k=3 column of A008278, but with offset n=0, is exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!).
Third row [1,4,3]: There are three plane increasing trees on 3 vertices. The number of colors are shown to the right of a vertex.
...................................................
....1o.(1+t)...........1o.t*(1+t).....1o.t*(1+t)...
....|................. /.\............/.\..........
....|................ /...\........../...\.........
....2o.(1+t)........2o.....3o......3o....2o........
....|..............................................
....|..............................................
....3o.............................................
...................................................
The total number of trees is (1+t)^2 + t*(1+t) + t*(1+t) = 1+4*t+3*t^2 = R(2,t).

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
Wolfdieter Lang, First ten rows.
MathOverflow, Recursion for row polynomials of A112493, (2025).
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

Row sums give A006351(k+1), k>=0.
The column sequences start with A000012 (powers of 1), A000295 (Eulerian numbers), A112495, A112496, A112497.
Cf. A008278, A008517, A048993, A054589, A075856, A134991, A201637, A124324.
Antidiagonal sums give A000110.
Cf. A356145.

T := (n, k) -> add(combinat:-eulerian2(n, j)*binomial(n-j, n-k), j=0..n):
seq(seq(T(n, k), k=0..n), n=0..9); # Peter Luschny, Apr 11 2016

max = 11; f[x_, t_] := -1 - (1 + t)/t*ProductLog[-t/(1 + t)*Exp[(x - t)/(1 + t)]]; coes = CoefficientList[ Series[f[x, t], {x, 0, max}, {t, 0, max}], {x, t}]* Range[0, max]!; Table[coes[[n, k]], {n, 0, max}, {k, 1, n - 1}] // Flatten (* Jean-François Alcover, Nov 22 2012, from e.g.f. *)

a(k, m) = 0 if k < m, a(k, -1):=0, a(0, 0)=1, a(k, m)=(m+1)*a(k-1, m) + (k+m-1)*a(k-1, m-1) else.
From Peter Bala, Sep 30 2011: (Start)
E.g.f.: A(x,t) = -1-((1+t)/t)*LambertW(-(t/(1+t))*exp((x-t)/(1+t))) = x + (1+t)*x^2/2! + (1+4*t+3*t^2)*x^3/3! + .... A(x,t) is the inverse function of (1+t)*log(1+x)-t*x.
A(x,t) satisfies the partial differential equation (1-x*t)*dA/dx = 1 + A + t*(1+t)*dA/dt. It follows that the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) =(n*t+1)*R(n,t) + t*(1+t)*dR(n,t)/dt. Cf. A054589 and A075856. The polynomials t/(1+t)*R(n,t) are the row polynomials of A134991.
The generating function A(x,t) satisfies the autonomous differential equation dA/dx = (1+A)/(1-t*A). Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees on n+1 vertices where the non-leaf vertices of outdegree k come in t^(k-1)*(1+t) colors. An example is given below. Cf. A006351, which corresponds to the case t = 1. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x) = (1+x)/(1-x*t). Then R(n,t) = (f(x)*d/dx)^n(f(x)) evaluated at x = 0. (End)
Sum_{j=0..n} T(n-j,j) = A000110(n). - Alois P. Heinz, Jun 20 2022
From Mikhail Kurkov, Apr 01 2025: (Start)
E.g.f.: B(y) = -w/(x*(1+w)) where w = LambertW(-x/(1+x)*exp((y-x)/(1+x))) satisfies the first-order ordinary differential equation (1+x)*B'(y) = B(y)*(1+x*B(y))^2, hence row polynomials are P(n,x) = P(n-1,x) + x*Sum_{j=0..n-1} binomial(n, j)*P(j,x)*P(n-j-1,x) for n > 0 with P(0,x) = 1 (see MathOverflow link).
Conjecture: row polynomials are P(n,x) = Sum_{i=0..n} Sum_{j=0..i} Sum_{k=0..j} (n+i)!*Stirling1(n+j-k,j-k)*x^k*(x+1)^(j-k)*(-1)^(j+k)/((n+j-k)!*(i-j)!*k!). (End)
Conjecture: g.f. satisfies 1/(1 - x - x*y/(1 - 2*x - 2*x*y/(1 - 3*x - 3*x*y/(1 - 4*x - 4*x*y/(1 - 5*x - 5*x*y/(1 - ...)))))) (see A383019 for conjectures about combinatorial interpretation and algorithm for efficient computing). - Mikhail Kurkov, Apr 21 2025

New name from Peter Luschny, Apr 11 2016

cp's OEIS Frontend

A112494 Sixth diagonal of the Stirling2 triangle A048993 and sixth column of triangle A008278.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Sage

Formula

A106340 Triangle T, read by rows, equal to the matrix inverse of the triangle defined by [T^-1](n,k) = (n-k)!*A008278(n+1,k+1), for n>=k>=0, where A008278 is a triangle of Stirling numbers of 2nd kind.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A106342 Matrix inverse of A008278, which is the reflected triangle of the Stirling numbers of 2nd kind.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A106343 Column 0 of triangle A106342, which is the matrix inverse of the triangle A008278 of Stirling numbers of 2nd kind.

Views

Author

Keywords

Crossrefs

Programs

PARI

A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Formula

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

A336420 Irregular triangle read by rows where T(n,k) is the number of divisors of the n-th superprimorial A006939(n) with distinct prime multiplicities and k prime factors counted with multiplicity.

Views

Author

Keywords