cp's OEIS Frontend

This is different from A080575 and A178867.

T(n,m) = count of set partitions of n with block lengths given by the m-th partition of n.

From Tilman Neumann, Oct 05 2008: (Start)

These are also the coefficients occurring in complete Bell polynomials, Faa di Bruno's formula (in its simplest form) and computation of moments from cumulants.

Though the Bell polynomials seem quite unwieldy, they can be computed easily as the determinant of an n-dimensional square matrix. (See, e.g., Coffey (2006) and program below.)

The complete Bell polynomial of the first n primes gives A007446. (End)

From Tom Copeland, Apr 29 2011: (Start)

A relation between partition polynomials formed from these "refined" Stirling numbers of the second kind and umbral operator trees and Lagrange inversion is presented in the link "Lagrange a la Lah".

For simple diagrams of the relation between connected graphs, cumulants, and A036040, see the references on statistical physics below. In some sense, these graphs are duals of the umbral bouquets presented in "Lagrange a la Lah". (End)

These M3 (Abramowitz-Stegun) partition polynomials are the complete Bell polynomials (see a comment above) with recurrence (see the Wikipedia link) B_0 = 1, B_n = Sum_{k=0..n-1} binomial(n-1,k) * B_{n-1-k}*x[k+1], n >= 1. - Wolfdieter Lang, Aug 31 2016

With the indeterminates (x_1, x_2, x_3,...) = (t, -c_2*t, -c_3*t, ...) with c_n > 0, umbrally B(n,a.) = B(n,t)|{t^n = a_n} = 0 and B(j,a.)B(k,a.) = B(j,t)B(k,t)|{t^n =a_n} = d_{j,k} >= 0 is the coefficient of x^j/j!*y^k/k! in the Taylor series expansion of the formal group law FGL(x,y) = f[f^{-1}(x)+f^{-1}(y)], where a_n are the inversion partition polynomials for calculating f(x) from the coefficients of the series expansion of f^{-1}(x) given in A134685. - Tom Copeland, Feb 09 2018

For applications to functionals in quantum field theory, see Figueroa et al., Brouder, Kreimer and Yeats, and Balduf. In the last two papers, the Bell polynomials with the indeterminates (x_1, x_2, x_3,...) = (c_1, 2!c_2, 3!c_3, ...) are equivalent to the partition polynomials of A130561 in the indeterminates c_n. - Tom Copeland, Dec 17 2019

From Tom Copeland, Oct 15 2020: (Start)

With a_n = n! * b_n = (n-1)! * c_n for n > 0, represent a function with f(0) = a_0 = b_0 = 1 as an

A) exponential generating function (e.g.f), or formal Taylor series: f(x) = e^{a.x} = 1 + Sum_{n > 0} a_n * x^n/n!

B) ordinary generating function (o.g.f.), or formal power series: f(x) = 1/(1-b.x) = 1 + Sum_{n > 0} b_n * x^n

C) logarithmic generating function (l.g.f): f(x) = 1 - log(1 - c.x) = 1 + Sum_{n > 0} c_n * x^n /n.

Expansions of log(f(x)) are given in

I) A127671 and A263634 for the e.g.f: log[ e^{a.*x} ] = e^{L.(a_1,a_2,...)x} = Sum_{n > 0} L_n(a_1,...,a_n) * x^n/n!, the logarithmic polynomials, cumulant expansion polynomials

II) A263916 for the o.g.f.: log[ 1/(1-b.x) ] = log[ 1 - F.(b_1,b_2,...)x ] = -Sum_{n > 0} F_n(b_1,...,b_n) * x^n/n, the Faber polynomials.

Expansions of exp(f(x)-1) are given in

III) A036040 for an e.g.f: exp[ e^{a.x} - 1 ] = e^{BELL.(a_1,...)x}, the Bell/Touchard/exponential partition polynomials, a.k.a. the Stirling partition polynomials of the second kind

IV) A130561 for an o.g.f.: exp[ b.x/(1-b.x) ] = e^{LAH.(b.,...)x}, the Lah partition polynomials

V) A036039 for an l.g.f.: exp[ -log(1-c.x) ] = e^{CIP.(c_1,...)x}, the cycle index polynomials of the symmetric groups S_n, a.k.a. the Stirling partition polynomials of the first kind.

Since exp and log are a compositional inverse pair, one can extract the indeterminates of the log set of partition polynomials from the exp set and vice versa. For a discussion of the relations among these polynomials and the combinatorics of connected and disconnected graphs/maps, see Novak and LaCroix on classical moments and cumulants and the two books on statistical mechanics referenced below. (End)

From Tom Copeland, Jun 12 2021: (Start)

These Bell polynomials and their relations to the Faa di Bruno Hopf bialgebra, correlation functions in quantum field theory, and the moment-cumulant duality are given on pp. 134 -144 of Zeidler.

An interpretation of the coefficients of the polynomials is given in expositions of the exponential formula, or principle, in Cameron et al., Duchamp, Duchamp et al., Labelle and Leroux, and Scott and Sokal along with some history. The simplest applications of this principle are given in A060540. (End)

This is different from A036040 and A178867.

T[n,m] = count of set partitions of n with block lengths given by the m-th partition of n in the canonical ordering.

From Tilman Neumann, Oct 05 2008: (Start)

These are also the coefficients occurring in complete Bell polynomials, Faa di Bruno's formula (in its simplest form) and computation of moments from cumulants.

Though the Bell polynomials seem quite unwieldy, they can be computed easily as the determinant of an n-dimensional square matrix. (see e.g. [Coffey] and program below)

The complete Bell polynomial of the first n primes gives A007446. (End)

The difference with A036040 and A178867 lies in the ordering of the monomials. This sequence uses lexicographic ordering, while in A036040 the total order (power) of the monomials prevails (Abramowitz-Stegun style): e.g., in row 6 we have ...+ 15*x[3]*x[5] + 15*x[3]*x[6]^2 + 10*x[4]^2 +...; in A036040 the coefficient of x[3]*x[6]^2 would come after that of x[4]^2 because the total order is higher, here it comes before in view of the lexicographic order. - M. F. Hasler, Jul 12 2015

"Standard order" here means as produced by Maple's "sort" command.

From Petros Hadjicostas, May 27 2020: (Start)

According to the Maple help files for the "sort" command, polynomials in multiple variables are "sorted in total degree with ties broken by lexicographic order (this is called graded lexicographic order)."

Thus for example, x_1^2*x_3 = x_1*x_1*x_3 > x_1*x_2*x_2 = x_1*x_2^2, while x_1^2*x_4 = x_1*x_1*x_4 > x_1*x_2*x_3. (End)

Row sums are 0 (for n > 1). Numbers of terms in rows are partition numbers A000041.

From Tom Copeland, Nov 06 2015: (Start)

With the formal Taylor series f(x) = 1 + x[1] x + x[2] x^2/2! + ... , the partition polynomials of this entry give d[log(f(x))]/dx = L_1(x[1]) + L_2(x[1], x[2]) x + L_3(...) x^2/2! + ..., and the coefficients of the reduced polynomials with x[n] = t are signed A028246.

The raising operator R = x + d[log(f(D)]/dD = x + L_1(x[1]) + L_2[x[1], x[2]) D + L_3(x[1], x[2], x[3]) D^2/2! + ... with D = d/dx generates an Appell sequence of polynomials, given umbrally by P_n(x[1], ..., x[n]; x) = (x[.] + x)^n = Sum_{k=0..n} binomial(n,k) x[k] * x^(n-k) = R^n 1 with the e.g.f. f(t)*e^(x*t) = exp[t P.(x[1], ..., x[.]; x)]. P_0 = x[0] = 1.

The umbral compositional inverse Appell sequence is generated by R = x - d[log(f(D))]/dD with e.g.f. e^(x*t)/f(t) = exp[t IP.(x[1], ..., x[.]; x)], so umbrally IP_n(x[1], ..., x[n]; P.(x[1], ..., x[n]; x)) = x^n = P_n(x[1], ..., x[n]; IP.(x[1], ..., x[n]; x)). An unsigned array for the reduced IP_n(x[1], ..., x[n]; x) polynomials with IP_0 = x[0] = 1 and x[n] = -1 for n > 0 is A154921, for which f(t) = 2 - e^t. (End)

From Tom Copeland, Sep 08 2016: (Start)

The Appell formalism allows a matrix representation in the power basis x^n of the raising operator R that incorporates this array's partition polynomials L_n(x[1], ..., x[n]):

VP_(n+1) = VP_n * R = VP_n * XPS^(-1) * MX * XPS, where XPS is the matrix formed from multiplying the n-th diagonal of the Pascal matrix PS of A007318 by the indeterminate x[n], with x[0] = 1 for the main diagonal of ones, i.e., XPS[n,k] = PS[n,k] * x[n-k]; the matrix MX is A129185; the matrix XPS^(-1) is the inverse of XPS, which can be formed by multiplying the diagonals of the Pascal matrix by the partition polynomials IPT(n, x[1], ..., x[n]) of A133314, i.e., XPS^(-1)[n,k] = PS[n,k] * IPT(n-k, x[1], ...); and VP_n is the row vector in the power basis representing the Appell polynomial P_n(x) formed from the basic sequence of moments 1, x[1], x[2], ..., i.e., umbrally P_n(x) = (x[.] + x)^n = Sum_{k=0..n} binomial(n,k) * x[k] * x^(n-k).

Then R = XPS^(-1) * MX * XPS is the Pascal matrix PS with an additional first superdiagonal of ones and the other lower diagonals multiplied by the partition polynomials of this array, i.e., R[n,k] = PS[n,k] * L_{n+1-k}(x[1], ..., x[n+1-k]) except for the first superdiagonal of ones.

Consistently, VP_n = (1, 0, 0, ...) * R^n = (1, 0, 0, ...) * XPS^(-1) * MX^n * XPS = (1, 0, 0, ...) * MX^n * XPS = the n-th row vector of XPS, which is the vector representation of P_n(x) = (x[.] + x)^n with x[0] = 1.

See the Copeland link for the umbral representation R = exp[g.*D] * x * exp[h.*D] that reflects the matrix representations.

The Stirling partition polynomials of the first kind St1_n(a[1], a[2], ..., a[n]) of A036039, the Stirling partition polynomials of the second kind St2_n(b[1], b[2], ..., b[n]) of A036040, and the refined Lah polynomials Lah_n[c[1], c[2], ..., c[n]) of A130561 are Appell sequences in the respective distinguished indeterminates a[1], b[1], and c[1]. Comparing the formulas for their raising operators with that in this entry, L_n(x[1], x[2], ..., x[n]) evaluates to

A) (n-1)! * a[n] for x[n] = St1_n(a[1], a[2], ..., a[n]);

B) b[n] for x[n] = St2_n(b[1], b[2], ..., b[n]);

C) n! * c[n] for x[n] = Lah_n(c[1], c[2], ..., c[n]).

Conversely, from the respective e.g.f.s (added Sep 12 2016)

D) x[n] = St1_n(L_1(x[1])/0!, ..., L_n(x[1], ..., x[n])/(n-1)!);

E) x[n] = St2_n(L_1(x[1]), ..., L_n(x[1], ..., x[n]));

F) x[n] = Lah_n(L_1(x[1])/1!, ..., L_n(x[1], ..., x[n])/n!).

Given only the Appell sequence with no closed form for the e.g.f., the raising operator can be generated using this formalism, as has been partially done for A134264. (End)

For the Appell sequences above, the raising operator is related to the recursion P_(n+1)(x) = x * P_n(x) + Sum_{k=0..n} binomial(n,k) * L_(n-k+1)(x[1], ..., x[n+k-1]) * P_k(x). For a derivation and connections to formal cumulants (c_n = L_n(x[1], ...)) and moments (m_n = x[n]), see the Copeland link on noncrossing partitions. With x = 0, the recursion reduces to x[n+1] = Sum_{k = 0..n} binomial(n,k) * L_(n-k+1)(x[1], ..., x[n+k-1]) * x[k] with x[0] = 1. This array is a differently ordered version of A127671. - Tom Copeland, Sep 13 2016

With x[n] = x^(n-1), a signed version of A130850 is obtained. - Tom Copeland, Nov 14 2016

See p. 2 of Getzler for a relation to stable graphs called necklaces used in computations for Deligne-Mumford-Knudsen moduli spaces of stable curves of genus 1. - Tom Copeland, Nov 15 2019

For a relation to a combinatorial Faa di Bruno Hopf algebra related to functional composition, as presented by Connes and Moscovici, see Figueroa et al. - Tom Copeland, Jan 17 2020

From Tom Copeland, May 17 2020: (Start)

The e.g.f. of an Appell sequence is f(t) e^(x*t) with f(0) = 1. Given the Laguerre-Polya class function f(t) = e^(-a*t^2 + b*t) Product_m (1 - t/z_m) e^(t/z_m) with a = 0 for simplicity (more generally a >= 0) and b real and where the product runs over all the zeros z_m of f(t) with all zeros real and Sum_m 1/(z_m)^2 convergent, the raising operator of the Appell polynomials is R = x + b - Sum_{k > 0} c_(k+1) D^k with c_k = Sum_m (1/(z_m)^k), i.e., traces of powers of the reciprocals of the zeros. From R in earlier comments, b = L_1(x_1) and otherwise c_k = -L_k(x_1, ..., x_k).

The Laguerre / Turan / de Gua inequalities (Csordas and Williamson and Skovgaard) imply that all the zeros of each Appell polynomial are real and simple and its extrema are local maxima above the x-axis and local minima below and are located above or below the zeros of the next lower degree Appell polynomial. (End)

From Tom Copeland, Oct 15 2020: (Start)

With a_n = n! * b_n = (n-1)! * c_n for n > 0, represent a function with f(0) = a_0 = b_0 = 1 as an

A) exponential generating function (e.g.f), or formal Taylor series: f(x) = e^{a.x} = 1 + Sum_{n > 0} a_n * x^n/n!

B) ordinary generating function (o.g.f.), or formal power series: f(x) = 1/(1-b.x) = 1 + Sum_{n > 0} b_n * x^n

C) logarithmic generating function (l.g.f): f(x) = 1 - log(1 - c.x) = 1 + Sum_{n > 0} c_n * x^n /n.

Expansions of log(f(x)) are given in

I) A127671 and A263634 for the e.g.f: log[ e^{a.*x} ] = e^{L.(a_1,a_2,...)x} = Sum_{n > 0} L_n(a_1,...,a_n) * x^n/n!, the logarithmic polynomials, cumulant expansion polynomials

II) A263916 for the o.g.f.: log[ 1/(1-b.x) ] = log[ 1 - F.(b_1,b_2,...)x ] = -Sum_{n > 0} F_n(b_1,...,b_n) * x^n/n, the Faber polynomials.

Expansions of exp(f(x)-1) are given in

III) A036040 for an e.g.f: exp[ e^{a.x} - 1 ] = e^{BELL.(a_1,...)x}, the Bell/Touchard/exponential partition polynomials, a.k.a. the Stirling partition polynomials of the second kind

IV) A130561 for an o.g.f.: exp[ b.x/(1-b.x) ] = e^{LAH.(b.,...)x}, the Lah partition polynomials

V) A036039 for an l.g.f.: exp[ -log(1-c.x) ] = e^{CIP.(c_1,...)x}, the cycle index polynomials of the symmetric groups S_n, a.k.a. the Stirling partition polynomials of the first kind.

Since exp and log are a compositional inverse pair, one can extract the indeterminates of the log set of partition polynomials from the exp set and vice versa. For a discussion of the relations among these polynomials and the combinatorics of connected and disconnected graphs/maps, see Novak and LaCroix on classical moments and cumulants and the two books on statistical mechanics referenced in A036040. (End)

Ignoring signs, these polynomials appear in Schröder in the set of equations (II) on p. 343 and in Stewart's translation on p. 31. - Tom Copeland, Aug 25 2021

The exponential transform [EXP] transforms an input sequence b(n) into the output sequence a(n). The EXP transform is the inverse of the logarithmic transform [LOG], see the Weisstein link and the Sloane and Plouffe reference. This relation goes by the name of Riddell's formula. For information about the logarithmic transform see A274805. The EXP transform is related to the multinomial transform, see A274760 and the second formula.

The definition of the EXP transform, see the second formula, shows that n >= 1. To preserve the identity LOG[EXP[b(n)]] = b(n) for n >= 0 for a sequence b(n) with offset 0 the shifted sequence b(n-1) with offset 1 has to be used as input for the exponential transform, otherwise information about b(0) will be lost in transformation.

In the a(n) formulas, see the examples, the multinomial coefficients A178867 appear.

We observe that a(0) = 1 and provides no information about any value of b(n), this notwithstanding it is customary to start the a(n) sequence with a(0) = 1.

The Maple programs can be used to generate the exponential transform of a sequence. The first program uses a formula found by Alois P. Heinz, see A007446 and the first formula. The second program uses the definition of the exponential transform, see the Weisstein link and the second formula. The third program uses information about the inverse of the exponential transform, see A274805.

Some EXP transform pairs are, n >= 1: A000435(n) and A065440(n-1); 1/A000027(n) and A177208(n-1)/A177209(n-1); A000670(n) and A075729(n-1); A000670(n-1) and A014304(n-1); A000045(n) and A256180(n-1); A000290(n) and A033462(n-1); A006125(n) and A197505(n-1); A053549(n) and A198046(n-1); A000311(n) and A006351(n); A030019(n) and A134954(n-1); A038048(n) and A053529(n-1); A193356(n) and A003727(n-1).

"Ordinary" here means in contrast to "exponential", cf. A178867 (see Comtet).

Graded lexicographic order with x[1] > x[2] > ... > x[n] means that monomials are compared first by their total degree, with ties broken by lexicographic order. These monomials correspond to integer partitions.

Row sums are powers of 2. Numbers of terms in rows are partition numbers A000041.

OP_n(-a_1,..,-a_n) = EP_n(a_1,2!*a_2,..,n!*a_n) / n!, where OP_n(a_1,..,a_n) are the partition polynomials of this entry and EP_n, the polynomials of A133314; i.e., the sequences are related as reciprocal o.g.f.s are to reciprocal e.g.f.s. The polynomials play a role in expansion of the iterated Lie derivative (g(x) D_x)^n) formalism for the compositional inversion sketched in A133932. With x[n] = t, the array reduces to the Pascal matrix A007318. - Tom Copeland, Sep 19 2016

The signed row partition polynomials can be generated by the Gram determinants of equation 2.23 on page 133 of the Verde-Star paper. E.g., h_3 = -b_1^3 + 2 b_1 b_2 - b_3 corresponds to the third row. The connection to A133314 is obtained by substituting a(k) = k!*b_k = -k!*x[k] and b(k) = k!*h_k in A133314 to compute reciprocals of o.g.f.s rather than e.g.f.s. - Tom Copeland, Dec 04 2016

For a relation to lambda operations in K-theory on vector bundles, see p. 218 of Dugger. - Tom Copeland, Jul 25 2017

Since E(x) = (1+x_1*x)(1+x_2*x)...(1+x_m*x) is the o.g.f. for the elementary symmetric polynomials e_n(x_1,x_2,...,x_m) and the o.g.f. for the complete symmetric polynomials h_n(x_1,x_2,...,x_m) is H(x) = 1 / E(-x), this entry's partition polynomials with correct signs give either sequence in terms of the other. - Tom Copeland, Jan 29 2018

A133314 has an interpretation as weighted surjective mappings. With the connections of this mapping colored and permuted to give mappings distinguished by the order of the colorings (an induced linear ordering by color of the connecting arrows), the signed partition polynomials of this entry, multiplied by n!, are generated. - Tom Copeland, Sep 10 2020

A generalization of the triangle of Stirling numbers of the second kind, these are the coefficients appearing in the expansion of (x_1 + x_2 + x_3 + ...)^n in terms of augmented monomial symmetric functions. They also appear in Faa di Bruno's formula.

All multinomial coefficients (MC's) are equal, but some are more equal than others. These are the basic multinomial coefficients (BMC's). The ordinary multinomial coefficients can be generated with the basic multinomial coefficients; see A178867.

A number n can be partitioned in A000041(n) different ways. The seven partitions of n=5 are e.g. [5] = [1+4] = [2+3] = [1+1+3] = [1+2+2] = [1+1+1+2] = [1+1+1+1+1]. We observe that the k-th partition of n will consist of a certain number of 1s (i.e., "singles"), a certain number of 2s (i.e., "pairs"), a certain number of 3s (i.e., "triples"), a certain number of 4s (i.e., "4-tuples") and so on. We denote with qt the number of t-tuples in the k-th partition of n. We observe that for the third partition of n=5 there is one pair (q2=1) and one triple (q3=1).

The multinomial coefficients are defined by M3[n,k] = n!/product((t!)^qt*(qt)!, t = 1..n), see Abramowitz and Stegun. For the third partition M3[5,3] = 10, so there are 10 different ways of distributing one pair (B1, B1) and one triple (B2, B2, B2) over five positions.

We define the BMC's as the multinomial coefficients M3[n,k] for which there are no singles (q1=0) in the k-th partition of n for n>=2. Furthermore we define a(1) = 1.

The number of a(n) terms in a triangle row lead to sequence A002865(n) (n>=2). The row sums lead to sequence A000296(n) (n>=2).

The phase space trajectory A276738 has phase space angular velocity A276814 and differential time dependence A276815. We calculate the period K = Int dt over the range [2*Pi, 0], trivial to compute from A276815 using A273496. Then K/(2*Pi) = 1 + sum b^(2n)*T(n,m)*f'(n,m); where the sum runs over n = 1, 2, 3 ... and m = 1, 2, 3, ... A000041(2n), and f'(n,m) = f(2n,m) of A276738 with Q=1/2. Choosing one point from the infinite dimensional coefficient space--v_i=0 for odd i, v_i=(-1)^(i/2-1)/2/(i!) otherwise--setting b^2 = 4*k, and summing over the entire table obtains the EllipticK expansion 2*A038534/A038533. For more details read "Plane Pendulum and Beyond by Phase Space Geometry" (Klee, 2016).

Name could also be "Triangle of multinomial coefficients, read by rows (version 4)", compare A036040, A080575, A178867. The latter and this one differ only in the order of columns.

The rows are counted from 1, the columns from 0.

Row lengths: 1,2,3,5,7,11... (partition numbers A000041)

Row sums: 1,2,5,15,52,203... (Bell numbers A000110)

Row maxima: 1,1,3,6,15,60,210,840,3780,12600,69300,415800... (A102356)

Distinct entries per row: 1,1,2,4,4,7,7,13,17,23,26,40... (A102465)

Rightmost columns are those from Pascal's triangle A007318 without the second one (i.e. triangle A184049). The other columns - (always?) without a 1 at the top - are multiples of these columns from Pascal's triangle; so actually only the top elements of each column are needed to calculate the other entries; these top elements are in A211360. (The top elements of the related triangle A178867 are in A178866.)