cp's OEIS Frontend

This sequence connects the multinomial coefficients A036040 (M_3) with A127671 (M_5).

The numbers of terms in n-th row is the number of partitions A000041(n). The number of terms T(n, k) with equal values in the n-th row follow the rhythm of A008284(n).

Some row sums are [1, 0, 2, -5, 21, -104, 636, -4511, 36455, -330954, 3334390, -36914039].

Also the number of logically distinct strings of first order quantifiers in which n variables occur (C. S. Peirce, c. 1903). - Stephen Pollard (spollard(AT)truman.edu), Jun 07 2002

Stirling transform of A052849(n) = [2, 4, 12, 48, 240, ...] is a(n) = [2, 6, 26, 150, 1082, ...]. - Michael Somos, Mar 04 2004

Stirling transform of A000142(n-1) = [1, 1, 2, 6, 24, ...] is a(n-1) = [1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004

Stirling transform of (-1)^n * A024167(n-1) = [0, 1, -1, 5, -14, 94, ...] is a(n-2) = [0, 1, 2, 6, 26, ...]. - Michael Somos, Mar 04 2004

The asymptotic expansion of 2*log(n) - (2^1*log(1) + 2^2*log(2) + ... + 2^n*log(n))/2^n is (a(1)/1)/n + (a(2)/2)/n^2 + (a(3)/3)/n^3 + ... - Michael Somos, Aug 22 2004

This is the sequence of cumulants of the probability distribution of the number of tails before the first head in a sequence of fair coin tosses. - Michael Hardy (hardy(AT)math.umn.edu), May 01 2005

Appears to be row sums of A154921. - Mats Granvik, Jan 18 2009

This is the number of cyclically ordered partitions of n+1 labeled points. The ordered version is A000670. - Michael Somos, Jan 08 2011

A000670(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012

Row sums of A154921 as conjectured above by Granvik. a(n) gives the number of outcomes of a race between n horses H1,...,Hn, where if a horse falls it is not ranked. For example, when n = 2 the 6 outcomes are a dead heat, H1 wins H2 second, H2 wins H1 second, H1 wins H2 falls, H2 wins H1 falls or both fall. - Peter Bala, May 15 2012

Also the number of disjoint areas of a Venn diagram for n multisets. - Aurelian Radoaca, Jun 27 2016

Also the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, and also comparing the smallest integers with 0. Each comparison with 0 gives two possibilities, x > 0 or x=0. As such, without comparison with 0, we get A000670, the number of ways of ordering n nonnegative integers, allowing for the possibility of ties, or the number of ways n competitors can rank in a competition, allowing for the possibility of ties. For instance, for 2 nonnegative integers x,y, there are the following 6 ways of ordering them: x = y = 0, x = y > 0, x > y = 0, x > y > 0, y > x = 0, y > x > 0. - Aurelian Radoaca, Jul 09 2016

Also the number of ordered set partitions of subsets of {1,...,n}. Also the number of chains of distinct nonempty subsets of {1,...,n}. - Gus Wiseman, Feb 01 2019

Number of combinations of a Simplex lock having n buttons.

Row sums of the unsigned cumulant expansion polynomials A127671 and logarithmic polynomials A263634. - Tom Copeland, Jun 04 2021

Also the number of vertices in the axis-aligned polytope consisting of all vectors x in R^n where, for all k in {1,...,n}, the k-th smallest coordinate of x lies in the interval [0, k]. - Adam P. Goucher, Jan 18 2023

Number of idempotent Boolean relation matrices whose complement is also idempotent. See Rosenblatt link. - Geoffrey Critzer, Feb 26 2023

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)

The list partition transform of a sequence a(n) for which a(0)=1 is illustrated by:

b_0 = 1

b_1 = -a_1

b_2 = -a_2 + 2 a_1^2

b_3 = -a_3 + 6 a_2 a_1 - 6 a_1^3

b_4 = -a_4 + 8 a_3 a_1 + 6 a_2^2 - 36 a_2 a_1^2 + 24 a_1^4

... .

The unsigned coefficients are A049019 with a leading 1. The sign is dependent on the partition as evident from inspection (replace a_n's by -1).

Expressed umbrally, i.e., with the umbral operation (a.)^n := a_n,

exp(a.x) exp(b.x) = exp[(a.+b.)x] = 1; i.e., (a.+b.)^n = 1 for n=0 and 0 for all other values of n.

Expressed recursively,

b_0 = 1, b_n = -Sum_{j=1..n} binomial(n,j) a_j b_{n-j}; which is conditionally self-inverse, i.e., the roles of a_k and b_k may be reversed with a_0 = b_0 = 1.

Expressed in matrix form, b_n form the first column of B = matrix inverse of A .

A = Pascal matrix diagonally multiplied by a_n, i.e., A_{n,k} = binomial(n,k)* a_{n-k}.

Some examples of reciprocal pairs of sequences under these operations are:

1) A084358 and -A000262 with the first term set to 1.

2) (1,-1,0,0,...) and (0!,1!,2!,3!,...) with the unsigned associated matrices A128229 and A094587.

3) (1,-1,-1,-1,...) and A000670.

4) A000110 and A000587.

5) (1,-2,-2,0,0,0,...) and (0! c_1,1! c_2,2! c_3,3! c_4,...) where c_n = A000129(n) with the associated matrices A110327 and A110330.

6) (1,-2,2,0,0,0,...) and (1!,2!,3!,4!,...).

7) Sequences of rising and signed lowering factorials form reciprocal pairs where a_n = (-1)^n m!/(m-n)! and b_n = (m-1+n)!/(m-1)! for m=0,1,2,... .

Denote the action of the list partition transform on the sequence a. or an invertible matrix M by LPT(a.) = b. or LPT(M)= M^(-1).

If the matrix equation M = exp(T) also holds, then exp[a.*T]*exp[b.*T] = exp[(a.+b.)*T] = I, the identity matrix, because (a.+b.)^n = delta_n, the Kronecker delta with delta_n = 1 and delta_n = 0 otherwise, i.e., (0)^n = delta_n.

Therefore, [exp(a.*T)]^(-1) = exp[b.*T] = exp[LPT(a.)*T] = LPT[exp(a.*T)].

The fundamental Pascal (A007318), unsigned Lah (A105278) and associated Laguerre matrices can be generated by exponentiation of special infinitesimal matrices (see A132440, A132710 and A132681) such that finding LPT(a.) amounts to multiplying the k'th diagonal of the fundamental matrices by a_k for every diagonal followed by matrix inversion and then extraction of the b_n factors from the first column (simplest for the Pascal formulas above).

Conversely, the inverses of matrices formed by diagonally multiplying the three fundamental matrices by a_k are given by diagonally multiplying the fundamental matrices by b_k.

If LPT(M) is defined differently as application of the top formula to a_n = M^n, then b_n = (-M)^n and the formalism could even be applied to more general sequences of matrices M., providing the reciprocal of exp[t*M.].

The group of fundamental lower triangular matrices M = exp(T) such that LPT[exp(a.*T)] = exp[LPT(a.)*T] = [exp[a.*T]]^(-1) are obtained by infinitesimal generator matrices of the form T =

0;

t(0), 0;

0, t(1), 0;

0, 0, t(2), 0;

0, 0, 0, t(3), 0;

... .

T^m has trivially vanishing terms except along the m'th subdiagonal, which is a sequence of generalized factorials:

[ t(0)*t(1)...t(m-2)*t(m-1), t(1)*t(2)...t(m-1)*t(m), t(2)*t(3)...t(m)*t(m+1), ... ].

Therefore the principal submatrices of T (given by setting t(j) = 0 for j > n-1) are nilpotent with at least [Tsub_n]^(n+1) = 0.

The general group of matrices GM[a.] = exp[a.*T] can also be obtained through diagonal multiplication of M = exp(T) by the sequence a_n, as in the Pascal matrix example above and their inverses by diagonal multiplication by b. = LPT(a.).

Weighted-mappings interpretation for the top partition equation:

Given n pre-nodes (Pre) and k post-nodes (Post), each Pre is connected to only one Post and each Post has at least one Pre connected to it (surjections or onto functions/maps). Weight each Post by -a_m where m is the number of connections to the Post.

Weight each map by the product of the Post weights and multiply by the number of maps that share the same connectivity. Sum over the possible mappings for n Pre. The result is b_n.

E.g., b_3 = [ 3 Pre to 1 Post ] + [ 3 Pre to 2 Post ] + [ 3 Pre to 3 Post ]

= [1 map with 1 Post with 3 connections] + [ 6 maps with 1 Post with 2 connections and 1 Post with 1 connection] + [6 maps with 3 Post with 1 connection each]

= -a_3 + 6 * [-a_2*(-a_1)] + 6 * [-a_1*(-a_1)*(-a_1)].

See A263633 for the complementary formulation for the reciprocal of o.g.f.s rather than e.g.f.s and computations of these partition polynomials as Gram determinants. - Tom Copeland, Dec 04 2016

The coefficients of the partition polynomials enumerate the faces of the convex, bounded polytopes called permutohedra, and the absolute value of the sum of the coefficients gives the Euler characteristic of unity for each polytope; i.e., the absolute value of the sum of each row of the array is unity. In addition, the signs of the faces alternate with dimension, and the coefficients of faces with the same dimension for each polytope have the same sign. - Tom Copeland, Nov 13 2019

With the fundamental matrix chosen to be the lower triangular Pascal matrix M, the matrix MA whose n-th diagonals are multiplied by a_n (i.e., MA_{i,j} = PM_{i,j} * a_{i-j}) gives a matrix representation of the e.g.f. associated to the Appell polynomial sequence defined by e^{a.t}e^{xt}= e^{(a.+x)t} = e^{A.(x)t} where umbrally (A.(x))^n = A_n(x) = (a. + x)^n = sum_{k=0..n} binomial(n,k) a_k x^{n-k} are the associated Appell polynomials. Left multiplication of the column vector (1,x,x^2,..) by MA gives the Appell polynomial sequence, and multiplication of the two e.g.f.s e^{a.t} and e^{b.t} corresponds to multiplication of their respective matrix representations MA and MB. Forming the reciprocal of an e.g.f. corresponds to taking the matrix inverse of its matrix representation as noted above. A263634 gives an associated modified Pascal matrix representation of the raising operator for the Appell sequence. - Tom Copeland, Nov 13 2019

The diagonal of MA consists of all ones. Let MAN be the truncated square submatrix of MA containing the coefficients of the first N Appell polynomials A_k=(a.+x)^k = Sum(j=0 to k) MAN(k,j) x^j. Then by the Cayley-Hamilton theorem (I-MAN)^N = 0; therefore, MAN^(-1) = Sum(k=1 to N) binomial(N,k) (-MAN)^{k-1} = MBN, the inverse of MAN, containing the coefficients of the first N rows of the Appell polynomials B_k(x) = (b. + x)^k = Sum(j=0 to k) MBN(k,j) x^j, which are the umbral compositional inverses of the Appell row polynomials A_k(x) of MAN; that is, A_k(B.(x)) = x^k = B_k(A.(x)), where, e.g., (A.(x))^k = A_k(x). - Tom Copeland, May 13 2020

The use of the term 'list partition transform' resulted from one of my first uses of these partition polynomials in relating A000262 to A084358 with their simple e.g.f.s. Other appropriate names would be the permutohedra polynomials since they are refined Euler characteristics of the permutohedra or the reciprocal polynomials since they give the multiplicative inverses of e.g.f.s with a constant of 1. - Tom Copeland, Oct 09 2022

The sequence of row lengths is A000041(n), n >= 1 (partition numbers).

Number of permutations whose cycle structure is the given partition. Row sums are factorials (A000142). - Franklin T. Adams-Watters, Jan 12 2006

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

These cycle index polynomials for the symmetric group S_n are also related to a raising operator / infinitesimal generator for fractional integro-derivatives, involving the digamma function and the Riemann zeta function values at positive integers, and to the characteristic polynomial for the adjacency matrix of complete n-graphs A055137 (cf. MathOverflow link). - Tom Copeland, Nov 03 2012

In the Lang link, replace all x(n) by t to obtain A132393. Furthermore replace x(1) by t and all other x(n) by 1 to obtain A008290. See A274760. - Tom Copeland, Nov 06 2012, Oct 29 2015 - corrected by Johannes W. Meijer, Jul 28 2016

The umbral compositional inverses of these polynomials are formed by negating the indeterminates x(n) for n>1, i.e., P(n,P(.,x(1),-x(2),-x(3),...),x(2),x(3),...) = x(1)^n (cf. A130561 for an example of umbral compositional inversion). The polynomials are an Appell sequence in x(1), i.e., dP(n,x(1))/dx(1) = n P(n-1, x(1)) and (P(.,x)+y)^n=P(n,x+y) umbrally, with P(0,x(1))=1. - Tom Copeland, Nov 14 2014

Regarded as the coefficients of the partition polynomials listed by Lang, a signed version of these polynomials IF(n,b1,b2,...,bn) (n! times polynomial on page 184 of Airault and Bouali) provides an inversion of the Faber polynomials F(n,b1,b2,...,bn) (page 52 of Bouali, A263916, and A115131). For example, F(3, IF(1,b1), IF(2,b1,b2)/2!, IF(3,b1,b2,b3)/3!) = b3 and IF(3, F(1,b1), F(2,b1,b2), F(3,b1,b2,b3))/3! = b3 with F(1,b1) = -b1. (Compare with A263634.) - Tom Copeland, Oct 28 2015; Sep 09 2016

The e.g.f. for the row partition polynomials is Sum_{n>=0} P_n(b_1,...,b_n) x^n/n! = exp[Sum_{n>=1} b_n x^n/n], or, exp[P.(b_1,...,b_n)x] = exp[-], expressed umbrally with <"power series"> denoting umbral evaluation (b.)^n = b_n within the power series. This e.g.f. is central to the paper by Maxim and Schuermannn on characteristic classes (cf. Friedrich and McKay also). - Tom Copeland, Nov 11 2015

The elementary Schur polynomials are given by S(n,x(1),x(2),...,x(n)) = P(n,x(1), 2*x(2),...,n*x(n)) / n!. See p. 12 of Carrell. - Tom Copeland, Feb 06 2016

These partition polynomials are also related to the Casimir invariants associated to quantum density states on p. 3 of Boya and Dixit and pp. 5 and 6 of Byrd and Khaneja. - Tom Copeland, Jul 24 2017

With the indeterminates (x_1,x_2,x_3,...) = (t,-c_2*t,-c_3*t,...) with c_n >0, umbrally P(n,a.) = P(n,t)|{t^n = a_n} = 0 and P(j,a.)P(k,a.) = P(j,t)P(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 A133932. - Tom Copeland, Feb 09 2018

For relation to the Witt symmetric functions, as well as the basic power, elementary, and complete symmetric functions, see the Borger link p. 295. For relations to diverse zeta functions, determinants, and paths on graphs, see the MathOverflow question Cycling Through the Zeta Garden. - Tom Copeland, Mar 25 2018

Chmutov et al. identify the partition polynomials of this entry with the one-part Schur polynomials and assert that any linear combination with constant coefficients of these polynomials is a tau function for the KP hierarchy. - Tom Copeland, Apr 05 2018

With the indeterminates in the partition polynomials assigned as generalized harmonic numbers, i.e., as partial sums of the Dirichlet series for the Riemann zeta function, zeta(n), for integer n > 1, sums of simple normalizations of these polynomials give either unity or simple sums of consecutive zeta(n) (cf. Hoffman). Other identities involving these polynomials can be found in the Choi reference in Hoffman's paper. - Tom Copeland, Oct 05 2019

On p. 39 of Ma Luo's thesis is the e.g.f. of rational functions r_n obtained through the (umbral) formula 1/(1-r.T) = exp[log(1+P.T)], a differently signed e.g.f. of this entry, where (P.)^n = P_n are Eisenstein elliptic functions. P. 38 gives the example of 4! * r_4 as the signed 4th row partition polynomial of this entry. This series is equated through a simple proportionality factor to the Zagier Jacobi form on p. 25. Recurrence relations for the P_n are given on p. 24 involving the normalized k-weight Eisenstein series G_k introduced on p. 23 and related to the Bernoulli numbers. - Tom Copeland, Oct 16 2019

The Chern characteristic classes or forms of complex vector bundles and the characteristic polynomials of curvature forms for a smooth manifold can be expressed in terms of this entry's partition polynomials with the associated traces, or power sum polynomials, as the indeterminates. The Chern character is the e.g.f. of these traces and so its coefficients are given by the Faber polynomials with this entry's partition polynomials as the indeterminates. See the Mathoverflow question "A canonical reference for Chern characteristic classes". - Tom Copeland, Nov 04 2019

For an application to the physics of charged fermions in an external field, see Figueroa et al. - Tom Copeland, Dec 05 2019

Konopelchenko, in Proposition 5.2, p. 19, defines an operator P_k that is a differently signed operator version of the partition polynomials of this entry divided by a factorial. These operators give rise to bilinear Hirota equations for the KP hierarchy. These partition polynomials are also presented in Hopf algebras of symmetric functions by Cartier. - Tom Copeland, Dec 18 2019

For relationship of these partition polynomials to calculations of Pontryagin classes and the Riemann xi function, see A231846. - Tom Copeland, May 27 2020

Luest and Skliros summarize on p. 298 many of the properties of the cycle index polynomials given here; and Bianchi and Firrotta, a few on p. 6. - Tom Copeland, Oct 15 2020

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)

Inverse binomial transform of A001006.

The Hankel transform of this sequence gives A000012 = [1,1,1,1,1,...].

Counts returning walks (excursions) of length n on a 1-d integer lattice with step set {+1,-1} which stay in the chamber x >= 0. - Andrew V. Sutherland, Feb 29 2008

Moment sequence of the trace of a random matrix in G=USp(2)=SU(2). If X=tr(A) is a random variable (A distributed according to the Haar measure on G) then a(n) = E[X^n]. - Andrew V. Sutherland, Feb 29 2008

Essentially the same as A097331. - R. J. Mathar, Jun 15 2008

Number of distinct proper binary trees with n nodes. - Chris R. Sims (chris.r.sims(AT)gmail.com), Jun 30 2010

-a(n-1), with a(-1):=0, n>=0, is the Z-sequence for the Riordan array A049310 (Chebyshev S). For the definition see that triangle. - Wolfdieter Lang, Nov 04 2011

See A180874 (also A238390 and A097610) and A263916 for relations to the general Bell A036040, cycle index A036039, and cumulant expansion polynomials A127671 through the Faber polynomials. - Tom Copeland, Jan 26 2016

A signed version is generated by evaluating polynomials in A126216 that are essentially the face polynomials of the associahedra. This entry's sequence is related to an inversion relation on p. 34 of Mizera, related to Feynman diagrams. - Tom Copeland, Dec 09 2019

Coefficients are listed in Abramowitz and Stegun order (A036036).

Given an invertible function f(t) analytic about t=0 (or a formal power series) with f(0)=0 and Df(0) not equal to 0, form h(t) = t / f(t) and let h_n denote the coefficient of t^n in h(t).

Lagrange inversion gives the compositional inverse about t=0 as g(t) = Sum_{j>=1} ( t^j * (1/j) * Sum_{permutations s with s(1) + s(2) + ... + s(j) = j - 1} h_s(1) * h_s(2) * ... * h_s(j) ) = t * T(1,1) * h_0 + Sum_{j>=2} ( t^j * Sum_{k=1..(# of partitions for j-1)} T(j,k) * H(j-1,k ; h_0,h_1,...) ), where H(j-1,k ; h_0,h_1,...) is the k-th partition for h_1 through h_(j-1) corresponding to n=j-1 on page 831 of Abramowitz and Stegun (ordered as in A&S) with (h_0)^(j-m)=(h_0)^(n+1-m) appended to each partition subsumed under n and m of A&S.

Denoting h_n by (n') for brevity, to 8th order in t,

g(t) = t * (0')

+ t^2 * [ (0') (1') ]

+ t^3 * [ (0')^2 (2') + (0') (1')^2 ]

+ t^4 * [ (0')^3 (3') + 3 (0')^2 (1') (2') + (0') (1')^3 ]

+ t^5 * [ (0')^4 (4') + 4 (0')^3 (1') (3') + 2 (0')^3 (2')^2 + 6 (0')^2 (1')^2 (2') + (0') (1')^4 ]

+ t^6 * [ (0')^5 (5') + 5 (0')^4 (1') (4') + 5 (0')^4 (2') (3') + 10 (0')^3 (1')^2 (3') + 10 (0')^3 (1') (2')^2 + 10 (0')^2 (1')^3 (2') + (0') (1')^5 ]

+ t^7 * [ (0')^6 (6') + 6 (0')^5 (1') (5') + 6 (0')^5 (2') (4') + 3 (0')^5 (3')^2 + 15 (0')^4 (1')^2 (4') + 30 (0')^4 (1') (2') (3') + 5 (0')^4 (2')^3 + 20 (0')^3 (1')^3 (3') + 30 (0')^3 (1')^2 (2')^2 + 15 (0')^2 (1')^4 (2') + (0') (1')^6]

+ t^8 * [ (0')^7 (7') + 7 (0')^6 (1') (6') + 7 (0')^6 (2') (5') + 7 (0')^6 (3') (4') + 21 (0')^5 (1')^2* (5') + 42 (0')^5 (1') (2') (4') + 21 (0')^5 (1') (3')^2 + 21 (0')^5 (2')^2 (3') + 35 (0')^4 (1')^3 (4') + 105 (0)^4 (1')^2 (2') (3') + 35 (0')^4 (1') (2')^3 + 35 (0')^3 (1')^4 (3') + 70 (0')^3 (1')^3 (2')^2 + 21 (0')^2 (1')^5 (2') + (0') (1')^7 ]

+ ..., where from the formula section, for example, T(8,1',2',...,7') = 7! / ((8 - (1'+ 2' + ... + 7'))! * 1'! * 2'! * ... * 7'!) are the coefficients of the integer partitions (1')^1' (2')^2' ... (7')^7' in the t^8 term.

A125181 is an extended, reordered version of the above sequence, omitting the leading 1, with alternate interpretations.

If the coefficients of partitions with the same exponent for h_0 are summed within rows, A001263 is obtained, omitting the leading 1.

From identification of the elements of the inversion with those on page 25 of the Ardila et al. link, the coefficients of the irregular table enumerate non-crossing partitions on [n]. - Tom Copeland, Oct 13 2014

From Tom Copeland, Oct 28-29 2014: (Start)

Operating with d/d(1') = d/d(h_1) on the n-th partition polynomial Prt(n;h_0,h_1,..,h_n) in square brackets above associated with t^(n+1) generates n * Prt(n-1;h_0,h_1,..,h_(n-1)); therefore, the polynomials are an Appell sequence of polynomials in the indeterminate h_1 when h_0=1 (a special type of Sheffer sequence).

Consequently, umbrally, [Prt(.;1,x,h_2,..) + y]^n = Prt(n;1,x+y,h_2,..); that is, Sum_{k=0..n} binomial(n,k) * Prt(k;1,x,h_2,..) * y^(n-k) = Prt(n;1,x+y,h_2,..).

Or, e^(x*z) * exp[Prt(.;1,0,h_2,..) * z] = exp[Prt(.;1,x,h_2,..) * z]. Then with x = h_1 = -(1/2) * d^2[f(t)]/dt^2 evaluated at t=0, the formal Laplace transform from z to 1/t of this expression generates g(t), the comp. inverse of f(t), when h_0 = 1 = df(t)/dt eval. at t=0.

I.e., t / (1 - t*(x + Prt(.;1,0,h_2,..))) = t / (1 - t*Prt(.;1,x,h_2,..)) = g(t), interpreted umbrally, when h_0 = 1.

(End)

Connections to and between arrays associated to the Catalan (A000108 and A007317), Riordan (A005043), Fibonacci (A000045), and Fine (A000957) numbers and to lattice paths, e.g., the Motzkin, Dyck, and Łukasiewicz, can be made explicit by considering the inverse in x of the o.g.f. of A104597(x,-t), i.e., f(x) = P(Cinv(x),t-1) = Cinv(x) / (1 + (t-1)*Cinv(x)) = x*(1-x) / (1 + (t-1)*x*(1-x)) = (x-x^2) / (1 + (t-1)*(x-x^2)), where Cinv(x) = x*(1-x) is the inverse of C(x) = (1 - sqrt(1-4*x)) / 2, a shifted o.g.f. for the Catalan numbers, and P(x,t) = x / (1+t*x) with inverse Pinv(x,t) = -P(-x,t) = x / (1-t*x). Then h(x,t) = x / f(x,t) = x * (1+(t-1)Cinv(x)) / Cinv(x) = 1 + t*x + x^2 + x^3 + ..., i.e., h_1=t and all other coefficients are 1, so the inverse of f(x,t) in x, which is explicitly in closed form finv(x,t) = C(Pinv(x,t-1)), is given by A091867, whose coefficients are sums of the refined Narayana numbers above obtained by setting h_1=(1')=t in the partition polynomials and all other coefficients to one. The group generators C(x) and P(x,t) and their inverses allow associations to be easily made between these classic number arrays. - Tom Copeland, Nov 03 2014

From Tom Copeland, Nov 10 2014: (Start)

Inverting in x with t a parameter, let F(x;t,n) = x - t*x^(n+1). Then h(x) = x / F(x;t,n) = 1 / (1-t*x^n) = 1 + t*x^n + t^2*x^(2n) + t^3*x^(3n) + ..., so h_k vanishes unless k = m*n with m an integer in which case h_k = t^m.

Finv(x;t,n) = Sum_{j>=0} {binomial((n+1)*j,j) / (n*j + 1)} * t^j * x^(n*j + 1), which gives the Catalan numbers for n=1, and the Fuss-Catalan sequences for n>1 (see A001764, n=2). [Added braces to disambiguate the formula. - N. J. A. Sloane, Oct 20 2015]

This relation reveals properties of the partitions and sums of the coefficients of the array. For n=1, h_k = t^k for all k, implying that the row sums are the Catalan numbers. For n = 2, h_k for k odd vanishes, implying that there are no blocks with only even-indexed h_k on the even-numbered rows and that only the blocks containing only even-sized bins contribute to the odd-row sums giving the Fuss-Catalan numbers for n=2. And so on, for n > 2.

These relations are reflected in any combinatorial structures enumerated by this array and the partitions, such as the noncrossing partitions depicted for a five-element set (a pentagon) in Wikipedia.

(End)

From Tom Copeland, Nov 12 2014: (Start)

An Appell sequence possesses an umbral inverse sequence (cf. A249548). The partition polynomials here, Prt(n;1,h_1,...), are an Appell sequence in the indeterminate h_1=u, so have an e.g.f. exp[Prt(.;1,u,h_2...)*t] = e^(u*t) * exp[Prt(.;1,0,h2,...)*t] with umbral inverses with an e.g.f e^(-u*t) / exp[Prt(.;1,0,h2,...)*t]. This makes contact with the formalism of A133314 (cf. also A049019 and A019538) and the signed, refined face partition polynomials of the permutahedra (or their duals), which determine the reciprocal of exp[Prt(.,0,u,h2...)*t] (cf. A249548) or exp[Prt(.;1,u,h2,...)*t], forming connections among the combinatorics of permutahedra and the noncrossing partitions, Dyck paths and trees (cf. A125181), and many other important structures isomorphic to the partitions of this entry, as well as to formal cumulants through A127671 and algebraic structures of Lie algebras. (Cf. relationship of permutahedra with the Eulerians A008292.)

(End)

From Tom Copeland, Nov 24 2014: (Start)

The n-th row multiplied by n gives the number of terms in the homogeneous symmetric monomials generated by [x(1) + x(2) + ... + x(n+1)]^n under the umbral mapping x(m)^j = h_j, for any m. E.g., [a + b + c]^2 = [a^2 + b^2 + c^2] + 2 * [a*b + a*c + b*c] is mapped to [3 * h_2] + 2 * [3 * h_1^2], and 3 * A134264(3) = 3 *(1,1)= (3,3) the number of summands in the two homogeneous polynomials in the square brackets. For n=3, [a + b + c + d]^3 = [a^3 + b^3 + ...] + 3 [a*b^2 + a*c^2 + ...] + 6 [a*b*c + a*c*d + ...] maps to [4 * h_3] + 3 [12 * h_1 * h_2] + 6 [4 * (h_1)^3], and the number of terms in the brackets is given by 4 * A134264(4) = 4 * (1,3,1) = (4,12,4).

The further reduced expression is 4 h_3 + 36 h_1 h_2 + 24 (h_1)^3 = A248120(4) with h_0 = 1. The general relation is n * A134264(n) = A248120(n) / A036038(n-1) where the arithmetic is performed on the coefficients of matching partitions in each row n.

Abramowitz and Stegun give combinatorial interpretations of A036038 and relations to other number arrays.

This can also be related to repeated umbral composition of Appell sequences and topology with the Bernoulli numbers playing a special role. See the Todd class link.

(End)

These partition polynomials are dubbed the Voiculescu polynomials on page 11 of the He and Jejjala link. - Tom Copeland, Jan 16 2015

See page 5 of the Josuat-Verges et al. reference for a refinement of these partition polynomials into a noncommutative version composed of nondecreasing parking functions. - Tom Copeland, Oct 05 2016

(Per Copeland's Oct 13 2014 comment.) The number of non-crossing set partitions whose block sizes are the parts of the n-th integer partition, where the ordering of integer partitions is first by total, then by length, then lexicographically by the reversed sequence of parts. - Gus Wiseman, Feb 15 2019

With h_0 = 1 and the other h_n replaced by suitably signed partition polynomials of A263633, the refined face partition polynomials for the associahedra of normalized A133437 with a shift in indices are obtained (cf. In the Realm of Shadows). - Tom Copeland, Sep 09 2019

Number of primitive parking functions associated to each partition of n. See Lemma 3.8 on p. 28 of Rattan. - Tom Copeland, Sep 10 2019

With h_n = n + 1, the d_k (A006013) of Table 2, p. 18, of Jong et al. are obtained, counting the n-point correlation functions in a quantum field theory. - Tom Copeland, Dec 25 2019

By inspection of the diagrams on Robert Dickau's website, one can see the relationship between the monomials of this entry and the connectivity of the line segments of the noncrossing partitions. - Tom Copeland, Dec 25 2019

Speicher has examples of the first four inversion partition polynomials on pp. 22 and 23 with his k_n equivalent to h_n = (n') here with h_0 = 1. Identifying z = t, C(z) = t/f(t) = h(t), and M(z) = f^(-1)(t)/t, then statement (3), on p. 43, of Theorem 3.26, C(z M(z)) = M(z), is equivalent to substituting f^(-1)(t) for t in t/f(t), and statement (4), M(z/C(z)) = C(z), to substituting f(t) for t in f^(-1)(t)/t. - Tom Copeland, Dec 08 2021

Given a Laurent series of the form f(z) = 1/z + h_1 + h_2 z + h_3 z^2 + ..., the compositional inverse is f^(-1)(z) = 1/z + Prt(1;1,h_1)/z^2 + Prt(2;1,h_1,h_2)/z^3 + ... = 1/z + h_1/z^2 + (h_1^2 + h_2)/z^3 + (h_1^3 + 3 h_1 h_2 + h_3)/z^4 + (h_1^4 + 6 h_1^2 h_2 + 4 h_1 h_3 + 2 h_2^2 + h_4)/z^5 + ... for which the polynomials in the numerators are the partition polynomials of this entry. For example, this formula applied to the q-expansion of Klein's j-invariant / function with coefficients A000521, related to monstrous moonshine, gives the compositional inverse with the coefficients A091406 (see He and Jejjala). - Tom Copeland, Dec 18 2021

The partition polynomials of A350499 'invert' the polynomials of this entry giving the indeterminates h_n. A multinomial formula for the coefficients of the partition polynomials of this entry, equivalent to the multinomial formula presented in the first four sentences of the formula section below, is presented in the MathOverflow question referenced in A350499. - Tom Copeland, Feb 19 2022

The coefficients of the Faber polynomials F(n,b(1),b(2),...,b(n)) (Bouali, p. 52) in the order of the partitions of Abramowitz and Stegun. Compare with A115131 and A210258.

These polynomials occur in discussions of the Virasoro algebra, univalent function spaces and the Schwarzian derivative, symmetric functions, and free probability theory. They are intimately related to symmetric functions, free probability, and Appell sequences through the raising operator R = x - d log(H(D))/dD for the Appell sequence inverse pair associated to the e.g.f.s H(t)e^(xt) (cf. A094587) and (1/H(t))e^(xt) with H(0)=1.

Instances of the Faber polynomials occur in discussions of modular invariants and modular functions in the papers by Asai, Kaneko, and Ninomiya, by Ono and Rolen, and by Zagier. - Tom Copeland, Aug 13 2019

The Faber polynomials, denoted by s_n(a(t)) where a(t) is a formal power series defined by a product formula, are implicitly defined by equation 13.4 on p. 62 of Hazewinkel so as to extract the power sums of the reciprocals of the zeros of a(t). This is the Newton identity expressing the power sum symmetric polynomials in terms of the elementary symmetric polynomials/functions. - Tom Copeland, Jun 06 2020

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)

Beginning with the second row, dividing each row by n gives the mirror of row n-1 of A141618. Under the exponential transform, the mirror of A141618 is generated, relating the number of connected graphs here to the number of disconnected graphs associated with A141618 (cf. A127671 and A036040). - Tom Copeland, Oct 25 2014

Let f(t) = u(t) - u(0) = Ev[exp(u.* t) - u(0)] = log{Ev[(exp(z.* t))/z_0]} = Ev[-log(1- a.* t)], where the operator Ev denotes umbral evaluation of the umbral variables u., z. or a., e.g., Ev[a.^n + a.^m] = a_n + a_m . The relation between z_n and u_n is given in reference in A127671 and u_n = (n-1)! * a_n .

If u_1 is not equal to 0, then the compositional inverse for these expressions is given by g(t) = Sum_{j>=1} P(j,t) where, with u_n denoted by (n') for brevity,

P(1,t) = (1')^(-1) * [ 1 ] * t

P(2,t) = (1')^(-3) * [ -(2') ] * t^2 / 2!

P(3,t) = (1')^(-5) * [ 3 (2')^2 - (1')(3') ] * t^3 / 3!

P(4,t) = (1')^(-7) * [ -15 (2')^3 + 10 (1')(2')(3') - (1')^2 (4') ] * t^4 / 4!

P(5,t) = (1')^(-9) * [ 105 (2')^4 - 105 (1') (2')^2 (3') + 10 (1')^2 (3')^2 + 15 (1')^2 (2') (4') - (1')^3 (5') ] * t^5 / 5!

P(6,t) = (1')^(-11) * [ -945 (2')^5 + 1260 (1') (2')^3 (3') - 280 (1')^2 (2') (3')^2 - 210 (1')^2 (2')^2 (4') + 35 (1')^3 (3')(4') + 21 (1')^3 (2')(5') - (1')^4 (6') ] * t^6 / 6!

P(7,t) = (1')^(-13) * [ 10395 (2')^6 - 17325 (1') (2')^4 (3') + (1')^2 [ 6300 (2')^2 (3')^2 + 3150 (2')^3 (4')] - (1')^3 [280 (3')^3 + 1260 (2')(3')(4') + 378 (2')^2(5')] + (1')^4 [35 (4')^2 + 56 (3')(5') + 28 (2')(6')] - (1')^5 (7') ] * t^7 / 7!

P(8,t) = (1')^(-15) * [ -135135 (2')^7 + 270270 (1') (2')^5 (3') - (1')^2 [ 138600 (2')^3 (3')^2 + 51975 (2')^4 (4')] + (1')^3 [15400 (2')(3')^3 + 34650 (2')^2(3')(4') + 6930 (2')^3(5')] - (1')^4 [2100 (3')^2(4') + 1575 (2')(4')^2 + 2520 (2')(3')(5') + 630 (2')^2(6') ] + (1')^5 [126 (4')(5') + 84 (3')(6') + 36 (2')(7')] - (1')^6 (8') ] * t^8 / 8!

...

Substituting ((m-1)') for (m') in each partition and ignoring the (0') factors, the partitions in the brackets of P(n,t) become those of n-1 listed in Abramowitz and Stegun on page 831 (in the reversed order) and the number of partitions in P(n,t) is given by A000041(n-1).

Combinatorial interpretations are given in the link.

From Tom Copeland, Jul 10 2018: (Start)

Coefficients occurring in prolongation for the special Euclidean group SE(2) and special affine group SA(2) in the Olver presentation on moving frames (MFP) in slides 33 and 42. These are a result of applying an iterated derivative of the form h(x)d/dx = d/dy as in this entry (more generally as g(x) d/dx as discussed in A145271). See also p. 6 of Olver's paper on contact forms, but note that the 12 should be a 15 in the formula for the compositional inverse of S(t).

Change variables in the MFP to obtain connections to the partition polynomials Prt_n = n! * P(n,1) above. Let delta and beta in the formulas for the equi-affine curves in MFP be L and B, respectively, and D_y = (1/(L-B*u_x)) d/dx = (1/w_x) d/dx. Then v_(yy) = (1/B) [-w_(xx)/(w_x)^3] in MFP (there is an overall sign error in MFP for v_(yy) and higher derivatives w.r.t. y), and (d/dy)^n v = v_n = (1/B)* [(1/w_1)*(d/dx)]^(n-2) [-w_2/(w_1)^3] for n > 1, with w_n = (d/dx)^n w. Consequently, in the partition polynomials Prt_n for n > 1 here substitute (n') = -B*u_n = w_n for n > 1 and (1') = L-B*u_1 = w_1, where u_n = (d/dx)^n u, and then divide by B. For example, v_4 = (1/B)*Prt_4 = (1/B)*4!*P(4,1) = (1/B) (L-B*u_n)^(-7) [-15*(-B*u_2)^3 + 10 (L-B*u_1)(-B*u_2)(-B*u_3) - (L-B*u_1)^2 (-B*u_4)], agreeing with v_4 in MFP except for the overall sign.

For the SE(2) transformation formulas in MFP, let w_x = cos(phi) + sin(phi)*u_x, and then the same transformations apply as above with cos(phi) and sin(phi) substituted for L and -B, respectively. (End)