cp's OEIS Frontend

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

Also known as Stirling set numbers.

S(n,k) enumerates partitions of an n-set into k nonempty subsets.

The o.g.f. for the sequence of diagonal k (k=0 for the main diagonal) is G(k,x) = ((x^k)/(1-x)^(2*k+1))*Sum_{m=0..k-1} A008517(k,m+1)*x^m. A008517 is the second-order Eulerian triangle. - Wolfdieter Lang, Oct 14 2005

From Philippe Deléham, Nov 14 2007: (Start)

Sum_{k=0..n} S(n,k)*x^k = B_n(x), where B_n(x) = Bell polynomials.

The first few Bell polynomials are:

B_0(x) = 1;

B_1(x) = 0 + x;

B_2(x) = 0 + x + x^2;

B_3(x) = 0 + x + 3x^2 + x^3;

B_4(x) = 0 + x + 7x^2 + 6x^3 + x^4;

B_5(x) = 0 + x + 15x^2 + 25x^3 + 10x^4 + x^5;

B_6(x) = 0 + x + 31x^2 + 90x^3 + 65x^4 + 15x^5 + x^6;

(End)

This is the Sheffer triangle (1, exp(x) - 1), an exponential (binomial) convolution triangle. The a-sequence is given by A006232/A006233 (Cauchy sequence). The z-sequence is the zero sequence. See the link under A006232 for the definition and use of these sequences. The row sums give A000110 (Bell), and the alternating row sums give A000587 (see the Philippe Deléham formulas and crossreferences below). - Wolfdieter Lang, Oct 16 2014

Also the inverse Bell transform of the factorial numbers (A000142). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

From Wolfdieter Lang, Feb 21 2017: (Start)

The transposed (trans) of this lower triagonal Sheffer matrix of the associated type S = (1, exp(x) - 1) (taken as N X N matrix for arbitrarily large N) provides the transition matrix from the basis {x^n/n!}, n >= 0, to the basis {y^n/n!}, n >= 0, with y^n/n! = Sum_{m>=n} S^{trans}(n, m) x^m/m! = Sum_{m>=0} x^m/m!*S(m, n).

The Sheffer transform with S = (g, f) of a sequence {a_n} to {b_n} for n >= 0, in matrix notation vec(b) = S vec(a), satisfies, with e.g.f.s A and B, B(x) = g(x)*A(f(x)) and B(x) = A(y(x)) identically, with vec(xhat) = S^{trans,-1} vec(yhat) in symbolic notation with vec(xhat)_n = x^n/n! (similarly for vec(yhat)).

(End)

For k >= 1 S(n, k) = h^{(k)}{n-k}, the complete homogeneous symmetric function of the k symbols 1,2, ..., k, of degree n-k. Thus S(n, k) is for k >= 1 the (dimensionless) volume of the multichoose(k, n-k) = binomial(n-1, k-1) polytopes of dimension n-k with (dimensionless) side lengths from the set {1, 2, ..., k}. See an example below. - _Wolfdieter Lang, May 26 2017

Number of partitions of {1, 2, ..., n+1} into k+1 nonempty subsets such that no subset contains two adjacent numbers. - Thomas Anton, Sep 26 2022

This version indexes the Eulerian numbers in the same way as Graham et al.'s Concrete Mathematics (see references section). The traditional indexing, used by Riordan, Comtet and others, is given in A008292, which is the main entry for the Eulerian numbers.

Each row of A123125 is the reverse of the corresponding row in A173018. - Michael Somos Mar 17 2011

Triangle T(n,k), read by rows, given by [1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,...] DELTA [0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,...] where DELTA is the operator defined in A084938. - Philippe Deléham Sep 30 2011

[ E(.,t)/(1-t)]^n = n!*Lag[n,-P(.,t)/(1-t)] and [ -P(.,t)/(1-t)]^n = n!*Lag[n, E(.,t)/(1-t)] umbrally comprise a combinatorial Laguerre transform pair, where E(n,t) are the Eulerian polynomials (e.g., E(2,t)= 1+t) and P(n,t) are the polynomials related to polylogarithms in A131758. - Tom Copeland, Oct 03 2014

See A131758 for connections of the evaluation of these polynomials at -1 (alternating row sum) to the Euler, Genocchi, Bernoulli, and zag/tangent numbers and values of the Riemann zeta function and polylogarithms. See also A119879 for the Swiss-knife polynomials. - Tom Copeland, Oct 20 2015

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.

A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016

Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004

Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008

Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018

From Gus Wiseman, Dec 28 2019: (Start)

Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:

{1,2,3,4} {{1},{2},{3,4}} {{1},{2,3,4}}

{{1},{2,3},{4}} {{1,2},{3,4}}

{{1,2},{3},{4}} {{1,2,3},{4}}

{{1},{2,4},{3}} {{1,2,4},{3}}

{{1,3},{2},{4}} {{1,3},{2,4}}

{{1,4},{2},{3}} {{1,3,4},{2}}

{{1,4},{2,3}}

{{{1},{2,3}},{4}}

{{{1,2},{3}},{4}}

{{1},{{2},{3,4}}}

{{1},{{2,3},{4}}}

{{{1},{2,4}},{3}}

{{{1,2},{4}},{3}}

{{1},{{2,4},{3}}}

{{{1,3},{2}},{4}}

{{{1},{3,4}},{2}}

{{{1,3},{4}},{2}}

{{{1,4},{2}},{3}}

{{{1,4},{3}},{2}}

(End)

Number of edges of the complete bipartite graph of order n+n^n, K_n,n^n. - Roberto E. Martinez II, Jan 07 2002

All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n >= 1. - Nick Hobson, Nov 30 2006

a(n) is also the number of ways of writing an n-cycle as the product of n+1 transpositions. - Nikos Apostolakis, Nov 22 2008

a(n) is the total number of elements whose preimage is the empty set summed over all partial functions from [n] into [n]. - Geoffrey Critzer, Jan 12 2022

Permutations avoiding 12-3 that contain the pattern 31-2 exactly once.

Kekulé numbers for certain benzenoids. - Emeric Deutsch, Nov 18 2005

Partial sums of A002411. - Jonathan Vos Post, Mar 16 2006

If Y is a 3-subset of an n-set X then, for n>=6, a(n-5) is the number of 6-subsets of X having at least two elements in common with Y. - Milan Janjic, Nov 23 2007

Starting with 1 = binomial transform of [1, 6, 12, 10, 3, 0, 0, 0, ...]. Equals row sums of triangle A143037. - Gary W. Adamson, Jul 18 2008

Rephrasing the Perry formula of 2003: a(n) is the sum of all products of all two numbers less than or equal to n, including the squares. Example: for n=3 the sum of these products is 1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25. - J. M. Bergot, Jul 16 2011

Half of the partial sums of A011379. [Jolley, Summation of Series, Dover (1961), page 12 eq (66).] - R. J. Mathar, Oct 03 2011

Also the number of (w,x,y,z) with all terms in {1,...,n+1} and w < x >= y > z (see A211795). - Clark Kimberling, May 19 2012

Convolution of A000027 with A000326. - Bruno Berselli, Dec 06 2012

This sequence is related to A000292 by a(n) = n*A000292(n) - Sum_{i=0..n-1} A000292(i) for n>0. - Bruno Berselli, Nov 23 2017

a(n-2) is the maximum number of intersections made from the perpendicular bisectors of all pair combinations of n points. - Ian Tam, Dec 22 2020

Starting with n=2, a(n) is the second-order Eulerian number <> (see A008517).

Also, number of 3 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1), (01;0) and (01;1). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1Sergey Kitaev, Nov 11 2004

This is the number of target DNA sequences of the correct length present after each successive cycle of the Polymerase Chain Reaction (PCR). The first two cycles produce 0 target sequences, there are 2 target sequences present after the third cycle, then 8 after the fourth cycle, and so forth. - A. Timothy Royappa, Jun 16 2012

a(n+2) = the row sums of A222403. - J. M. Bergot, Apr 04 2018

n-th row of the triangle = charpoly of an (n-1) X (n-1) matrix with (1,2,3,...) in the diagonal and the rest zeros. - Gary W. Adamson, Mar 19 2009

From Daniel Forgues, Jan 16 2016: (Start)

For n >= 1, 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)

The moment generating function of the probability density function p(x, m=q, n=1, mu=q) = q^q*x^(q-1)*E(x, q, 1)/(q-1)!, with q >= 1, is M(a, m=q, n=1, mu=q) = Sum_{k=0..q}(A000312(q) / A000142(q-1)) * A008276(q, k) * polylog(k, a) / a^q , see A163931 and A274181. - Johannes W. Meijer, Jun 17 2016

Triangle of coefficients of the polynomial x(x-1)(x-2)...(x-n+1), also denoted as falling factorial (x)n, expanded into decreasing powers of x. - _Ralf Stephan, Dec 11 2016

This is the row reversed second-order Eulerian triangle A008517(k+1,k+1-m). For references see A008517.

The o.g.f. for the k-th diagonal, k >= 1, of the unsigned Stirling1 triangle |A008275| is G1(1,x)=1/(1-x) if k=1 and G1(k,x) = g1(k-2,x)/(1-x)^(2*k-1), if k >= 2, with the row polynomials g1(k;x):=Sum_{m=0..k} a(k,m)*x^m.

The recurrence eq. for the row polynomials is g1(k,x)=((k+1)+k*x)*g1(k-1,x) + x*(1-x)*(d/dx)g1(k-1,x), k >= 1, with input g1(0,x):=1.

The column sequences start with A000142 (factorials), A002538, A002539, A112008, A112485.

This o.g.f. computation was inspired by Bender et al. article where the Stirling polynomials have been rediscussed.

The A163936 triangle is identical to the triangle given above except for an extra right hand column [1, 0, 0, 0, ... ]. The A163936 triangle is related to the higher order exponential integrals E(x,m,n), see A163931 and A163932. - Johannes W. Meijer, Oct 16 2009

The n-th row also gives the coefficients of the sigma polynomial of the empty graph \bar K_n. - Eric W. Weisstein, Apr 07 2017

The n-th row also gives the coefficients of the independence polynomial of the (n-1)-triangular honeycomb bishop graph. - Eric W. Weisstein, Apr 03 2018

From Gus Wiseman, Aug 11 2020: (Start)

Conjecture: also the number of divisors of the superprimorial A006939(n - 1) that have 0 <= k <= n distinct prime factors, all appearing with distinct multiplicities. For example, row n = 4 counts the following divisors of 360:

1 2 12 360

3 18

4 20

5 24

8 40

9 45

72

Equivalently, T(n,k) is the number of length-n vectors 0 <= v_i <= i with k nonzero values, all of which are distinct.

Crossrefs:

A006939 lists superprimorials or Chernoff numbers.

A022915 counts permutations of prime indices of superprimorials.

A076954 can be used instead of A006939.

A130091 lists numbers with distinct prime multiplicities.

A181796 counts divisors with distinct prime multiplicities.

A336420 is the version counting all prime factors, not just distinct ones.

Cf. A000005, A027423, A095149, A124010, A317829, A327498, A336419, A336421.

(End)

From Leonidas Liponis, Aug 26 2024: (Start)

It appears that this sequence is related to the combinatorial form of Faà di Bruno's formula. Specifically, the number of terms for the n-th derivative of a composite function y = f(g(x)) matches the number of partitions of n.

For example, consider the case where g(x) = e^x, in which all derivatives of g(x) are equal. The first 5 rows of A008278 appear as the factors of derivatives of f(x), highlighted here in brackets:

dy/dx = [ 1 ] * f'(e^x) * e^x

d^2y/dx^2 = [ 1 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^3y/dx^3 = [ 1 ] * f'''(e^x) * e^{3x} + [ 3 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^4y/dx^4 = [ 1 ] * f''''(e^x) * e^{4x} + [ 6 ] * f'''(e^x) * e^{3x} + [ 7 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^5y/dx^5 = [ 1 ] * f'''''(e^x) * e^{5x} + [ 10 ] * f''''(e^x) * e^{4x} + [ 25 ] * f'''(e^x) * e^{3x} + [ 15 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

This pattern is observed in Mathematica for the first 10 cases, using the code below.

(End)