cp's OEIS Frontend

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 n-th row has partition(n) = A000041(n) entries.

Also the numbers of standard Young tableaux for Young diagrams (or partitions).

Also "generalized" Catalan numbers. For a partition of n, n=(n_1+...+n_d), this is the number of integral lattice paths from (0,...,0) to (n_1,...,n_d) such that for any point p=(p_1,...p_d) on such a path p_i is never less than p_j whenever iGraham H. Hawkes, Jul 05 2013

The irreducible representations of S_n correspond to Young diagrams or partitions.

Partitions of n are ordered according to Abramowitz-Stegun (A-St) (see the reference, pp. 831-2). In contrast to A-St, a partition has nondecreasing parts (reverse notation of A-St).

The dimension of a representation of S_n corresponding to a Young diagram or partition is a(n,k) for the k-th partition of n in this A-St order.

One could call these numbers a(n,k) M_4 (similar to M_0, M_1, M_2, M_3 given in A111786, A036038, A036039, A036040, respectively).

From Wolfdieter Lang, Oct 09 2015: (Start)

The first formula given below appears in A. Young, Q.S.A. III, PLMS 28 (1928) 255-292 (third paper on "On Quantitative Substitutional Analysis"), Theorem II on p. 260, and he calls it f; see the collected papers (CP) reference, p. 357. Note the shorthand notation for the products; see Q.S.A. II, PLMS 34 (1902) 361-397, p. 366, CP, p. 97, for the explicit one.

This formula also can be found in the Glass-Ng link, Theorem 1, p. 702, using the Vandermonde determinant in the numerator and re-indexing the denominator.

The product of the hook length numbers, called H(n, k) in this formula below, is found in A263003(n, k).

The squared row entries sum to n!. See A. Young, Q.S.A. II (see above), pp. 367-368, CP pp. 98-99. Also Q.S.A. III, p. 265, CP p. 362.

(End)

Starting (1, 2, 9, 24, ...) = row sums of triangle A156792. - Gary W. Adamson, Feb 15 2009

Equals signed A006973 (except for initial term), where A006973 lists the dimensions of representations by Witt vectors.

The order of this array is according to the Abramowitz-Stegun (A-St) ordering of partitions (see A036036).

The row lengths sequence is A000041 (partition numbers) [1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ...].

These numbers are similar to M_0, M_1, M_2, M_3, M_4 given in A111786, A036038, A036039, A036040, A117506, respectively.

Combinatorial interpretation: a(n,k) counts the sets of lists (ordered subsets) obtained from partitioning the set {1..n}, with the lengths of the lists given by the k-th partition of n in A-St order. E.g., a(5,5) is computed from the number of sets of lists of lengths [1^1,2^2] (5th partition of 5 in A-St order). Hence a(5,5) = binomial(5,2)*binomial(3,2) = 5!/(1!*2!) = 60 from partitioning the numbers 1,2,...,5 into sets of lists of the type {[.],[..],[..]}.

This array, called M_3(2), is the k=2 member of a family of partition arrays generalizing A036040 which appears as M_3 = M_3(k=1). S2(2) = A105278 (unsigned Lah number triangle) is related to M_3(2) in the same way as S2(1), the Stirling2 number triangle, is related to M_3(1). - Wolfdieter Lang, Oct 19 2007

Another combinatorial interpretation: a(n,k) enumerates unordered forests of increasing binary trees which are described by the k-th partition of n in the Abramowitz-Stegun order. - Wolfdieter Lang, Oct 19 2007

A relation between partition polynomials formed from these "refined Lah numbers" and Lagrange inversion for an o.g.f. is presented in the link "Lagrange a la Lah" along with an e.g.f. and an umbral binary operator tree representation. - Tom Copeland, Apr 12 2011

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 A133437. - Tom Copeland, Feb 09 2018

Divided by n!, the row partition polynomials are the elementary homogeneous Schur polynomials presented on p. 44 of the Bracci et al. paper. - Tom Copeland, Jun 04 2018

Also presented (renormalized) as the Schur polynomials on p. 19 of the Konopelchenko and Schief paper with associations to differential operators related to the KP hierarchy. - Tom Copeland, Nov 19 2018

Through equation 4.8 on p. 26 of the Arbarello reference, these polynomials appear in the Hirota bilinear equations 4.7 related to tau-function solutions of the KP hierarchy. - Tom Copeland, Jan 21 2019

These partition polynomials appear as Feynman amplitudes in their Bell polynomial guise (put x_n = n!c_n in A036040 for the indeterminates of the Bell polynomials) in Kreimer and Yeats and Balduf (e.g., p. 27). - 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 in A036040. (End)

These partition polynomials are referred to as Schur functions by Segal and Wilson, who present associations with Plucker coordinates, Grassmannians, and the tau functions of the KdV hierarchy. See pages 51 and 61. - Tom Copeland, Jan 08 2022

This is a function of the individual partitions of an integer. The number of values in each line is given by A000041; thus lines 0 to 5 of the sequence are (1), (1), (1,2), (1,3,6), (1,4,6,12,24). The partitions in each line are ordered with the largest part sizes first, so the line 4 indices are [4], [3,1], [2,2], [2,1,1] and [1,1,1,1]. Note that exponents are often used to represent repeated values in a partition, so the last index could instead be written [1^4]. The combination function (sequence A007318) C(n,m) = C([m,n-m]).

This sequence is also the sequence of multinomial coefficients for partitions ordered lexicographically, matching partition sequence A080577. This is different ordering than in sequence A036038 of multinomial coefficients. - Sergei Viznyuk, Mar 15 2012

Connected objects from general (disconnected) objects.

The row lengths of this array is p(n):=A000041(n) (partition numbers).

In row n the partitions of n are taken in the Abramowitz-Stegun order.

One could call the unsigned numbers |a(n,k)| M_5 (similar to M_0, M_1, M_2, M_3 and M_4 given in A111786, A036038, A036039, A036040 and A117506, resp.).

The inverse relation (disconnected from connected objects) is found in A036040.

(d/da(1))p_n[a(1),a(2),...,a(n)] = n b_(n-1)[a(1),a(2),...,a(n-1)], where p_n are the partition polynomials of the cumulant generator A127671 and b_n are the partition polynomials for A133314. - Tom Copeland, Oct 13 2012

See notes on relation to Appell sequences in a differently ordered version of this array A263634. - Tom Copeland, Sep 13 2016

Given a binomial Sheffer polynomial sequence defined by the e.g.f. exp[t * f(x)] = Sum_{n >= 0} p_n(t) * x^n/n!, the cumulants formed from these polynomials are the Taylor series coefficients of f(x) multipied by t. An example is the sequence of the Stirling polynomials of the first kind A008275 with f(x) = log(1+x), so the n-th cumulant is (-1)^(n-1) * (n-1)! * t. - Tom Copeland, Jul 25 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 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

This is a refinement of A019538 with row sums in A000670.

From Tom Copeland, Sep 29 2008: (Start)

This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth-order term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(-5) * {24 a(1)^4 - 36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2 - a(4) a(0)^3}.

The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron.

Given the n X n lower triangular matrix M = [ binomial(j,k) u(j-k) ], the first column of the inverse matrix M^(-1) contains the (n-1) rows of A049019 as the coefficients of the multinomials formed from the u(j). M^(-1) can be computed as (1/u(0)){I - [I- M/u(0)]^n} / {I - [I- M/u(0)]} = - u(0)^(-n) {sum(j=1 to n)(-1)^j bin(n,j) u(0)^(n-j) M^(j-1)} where I is the identity matrix.

Another method for computing the coefficients and partitions up to (n-1) rows is to use (1-x^n)/ (1-x) = 1+x^2+x^3+ ... + x^(n-1) with x replaced either by [I- M/a(0)] or [1- g(x)/a(0)] with the n X n matrix M = [bin(j,k) a(j-k)] and g(x)= a(0) + a(1)x + a(2)x^2/2! + ... + a(n) x^n/n!. The first n terms (rows of the first column) of the resulting series (matrix) divided by a(0) contain the (n-1) rows of signed coefficients and associated partitions for A049019.

To obtain unsigned coefficients, change a(j) to -a(j) for j>0. A133314 contains other matrices and recursion formulas that could be used. The Faa di Bruno formula gives the coefficients as n! [e(1)+e(2)+...+e(n)]! / [1!^e(1) e(1)! 2!^e(2) e(2)!... n!^e(n) e(n)! ] for the partition of form [a(1)^e(1)...a(n)^e(n)] with [e(1)+2e(2)+...+ n e(n)] = n (see Abramowitz and Stegun pages 823 and 831) in agreement with Arnold's formula. (End)

N*t^{(N)}n(sigma_1, ..., sigma_N):= sum((x_k)^n, k=1..N) with the elementary symmetric function sigma_k (superscript (N) omitted) in terms of the indeterminates x_1,...,x_N, is an N-variable generalization of Chebyshev's polynomials C_n((sigma_1)/2) = t^{(N=2)}_n(sigma_1, sigma_2 = 1). In general, C_n^{(N)}(sigma_1, ..., sigma{N-1}) := t^{(N)}n(sigma_1, ..., sigma{N-1}, sigma_N:=1). If n > N, one puts sigma_{N+1} = 0, ..., sigma_n = 0.

The sequence of row lengths of this array is A000041(n) (partition numbers).

In row n, this triangular array uses partitions of n listed in the Abramowitz-Stegun order (compare with the M_0, M_1, M_2 and M_3 numbers given in A048996 = |A111786|, A036038, A036039 and A036040, resp.).

Row sums give (-1)^(n-1). Unsigned row sums give A000225(n)= 2^n - 1.

N*t^{(N)}n(sigma_1, ..., sigma_N) gives the sum of the n-th power of the indeterminates x_1, ... , x_N in terms of the elementary symmetric functions of these indeterminates. The coefficient T(n, k) of this partition array corresponds to the k-th partition of n in the Abramowitz-Stegun order, and it multiplies the product of sigma_j functions encoded by this partition. See the example for n = 4 below. - _Wolfdieter Lang, Mar 09 2015