cp's OEIS Frontend

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

T(n,m) is the number of m-faces of a regular n-simplex.

An n-simplex is the n-dimensional analog of a triangle. Specifically, a simplex is the convex hull of a set of (n + 1) affinely independent points in some Euclidean space of dimension n or higher, i.e., a set of points such that no m-plane contains more than (m + 1) of them. Such points are said to be in general position.

Reversing the rows gives A074909, which as a linear sequence is essentially the same as this.

From Tom Copeland, Dec 07 2007: (Start)

T(n,k) * (k+1)! = A068424. The comment on permuted words in A068424 shows that T is related to combinations of letters defined by connectivity of regular polytope simplexes.

If T is the diagonally-shifted Pascal matrix, binomial(n+m, k+m), for m=1, then T is a fundamental type of matrix that is discussed in A133314 and the following hold.

The infinitesimal matrix generator is given by A132681, so T = LM(1) of A132681 with inverse LM(-1).

With a(k) = (-x)^k / k!, T * a = [ Laguerre(n,x,1) ], a vector array with index n for the Laguerre polynomials of order 1. Other formulas for the action of T are given in A132681.

T(n,k) = (1/n!) (D_x)^n (D_t)^k Gf(x,t) evaluated at x=t=0 with Gf(x,t) = exp[ t * x/(1-x) ] / (1-x)^2.

[O.g.f. for T ] = 1 / { [ 1 - t * x/(1-x) ] * (1-x)^2 }. [ O.g.f. for row sums ] = 1 / { (1-x) * (1-2x) }, giving A000225 (without a leading zero) for the row sums. Alternating sign row sums are all 1. [Sign correction noted by Vincent J. Matsko, Jul 19 2015]

O.g.f. for row polynomials = [ (1+q)**(n+1) - 1 ] / [ (1+q) -1 ] = A(1,n+1,q) on page 15 of reference on Grassmann cells in A008292. (End)

Given matrices A and B with A(n,k) = T(n,k)*a(n-k) and B(n,k) = T(n,k)*b(n-k), then A*B = C where C(n,k) = T(n,k)*[a(.)+b(.)]^(n-k), umbrally. The e.g.f. for the row polynomials of A is {(a+t) exp[(a+t)x] - a exp(a x)}/t, umbrally. - Tom Copeland, Aug 21 2008

A007318*A097806 as infinite lower triangular matrices. - Philippe Deléham, Feb 08 2009

Riordan array (1/(1-x)^2, x/(1-x)). - Philippe Deléham, Feb 22 2012

The elements of the matrix inverse are T^(-1)(n,k)=(-1)^(n+k)*T(n,k). - R. J. Mathar, Mar 12 2013

Relation to K-theory: T acting on the column vector (-0,d,-d^2,d^3,...) generates the Euler classes for a hypersurface of degree d in CP^n. Cf. Dugger p. 168 and also A104712, A111492, and A238363. - Tom Copeland, Apr 11 2014

Number of walks of length p>0 between any two distinct vertices of the complete graph K_(n+2) is W(n+2,p)=(-1)^(p-1)*Sum_{k=0..p-1} T(p-1,k)*(-n-2)^k = ((n+1)^p - (-1)^p)/(n+2) = (-1)^(p-1)*Sum_{k=0..p-1} (-n-1)^k. This is equal to (-1)^(p-1)*Phi(p,-n-1), where Phi is the cyclotomic polynomial when p is an odd prime. For K_3, see A001045; for K_4, A015518; for K_5, A015521; for K_6, A015531; for K_7, A015540. - Tom Copeland, Apr 14 2014

Consider the transformation 1 + x + x^2 + x^3 + ... + x^n = A_0*(x-1)^0 + A_1*(x-1)^1 + A_2*(x-1)^2 + ... + A_n*(x-1)^n. This sequence gives A_0, ..., A_n as the entries in the n-th row of this triangle, starting at n = 0. - Derek Orr, Oct 14 2014

See A074909 for associations among this array, the Bernoulli polynomials and their umbral compositional inverses, and the face polynomials of permutahedra and their duals (cf. A019538). - Tom Copeland, Nov 14 2014

From Wolfdieter Lang, Dec 10 2015: (Start)

A(r, n) = T(n+r-2, r-1) = risefac(n,r)/r! = binomial(n+r-1, r), for n >= 1 and r >= 1, gives the array with the number of independent components of a symmetric tensors of rank r (number of indices) and dimension n (indices run from 1 to n). Here risefac(n, k) is the rising factorial.

As(r, n) = T(n+1, r+1) = fallfac(n, r)/r! = binomial(n, r), r >= 1 and n >= 1 (with the triangle entries T(n, k) = 0 for n < k) gives the array with the number of independent components of an antisymmetric tensor of rank r and dimension n. Here fallfac is the falling factorial. (End)

The h-vectors associated to these f-vectors are given by A000012 regarded as a lower triangular matrix. Read as bivariate polynomials, the h-polynomials are the complete homogeneous symmetric polynomials in two variables, found in the compositional inverse of an e.g.f. for A008292, the h-vectors of the permutahedra. - Tom Copeland, Jan 10 2017

For a correlation between the states of a quantum system and the combinatorics of the n-simplex, see Boya and Dixit. - Tom Copeland, Jul 24 2017

A000295 (Eulerian numbers) gives the row sums.

Write A004736 and Pascal's triangle as infinite lower triangular matrices A and B; then A*B is this triangle.

From Peter Luschny, Apr 10 2011: (Start)

A slight variation has a combinatorial interpretation: remove the last column and the second one from Pascal's triangle. Let P(m, k) denote the set partitions of {1,2,..,n} with the following properties:

(a) Each partition has at least one singleton block;

(c) k is the size of the largest block of the partition;

(b) m = n - k + 1 is the number of parts of the partition.

Then A000295(n) = Sum_{k=1..n} card(P(n-k+1,k)).

For instance, A000295(4) = P(4,1) + P(3,2) + P(2,3) + P(1,4) = card({1|2|3|4}) + card({1|2|34, 1|3|24,1|4|23, 2|3|14, 2|4|13, 3|4|12}) + card({1|234, 2|134, 3|124, 4|123}) = 1 + 6 + 4 = 11.

This interpretation can be superimposed on the sequence by changing the offset to 1 and adding the value 1 in front. The triangle then starts

1;

1, 3;

1, 6, 4;

1, 10, 10, 5;

1, 15, 20, 15, 6;

...

(End)

Diagonal sums are A001924(n+1). - Philippe Deléham, Jan 11 2014

Relation to K-theory: T acting on the column vector (d,-d^2,d^3,...) generates the Euler classes for a hypersurface of degree d in CP^n. Cf. Dugger p. 168, A111492, A238363, and A135278. - Tom Copeland, Apr 11 2014

Analogous to the infinitesimal generators of A132681 and A132792.

The matrix T begins

0;

2, 0;

0, 6, 0;

0, 0, 12 0;

0, 0, 0, 20, 0;

Along the nonvanishing diagonal the n-th term is (n+2)*(n+1).

Let LM(t) = exp(t*T) = lim_{n->infinity} (1 + t*T/n)^n.

Shifted Lah matrix = [bin(n+1,k+1)*(n)!/(k)! ] = LM(1) = exp(T). Truncating the series gives the n X n submatrices. In fact, the submatrices of T are nilpotent with [Tsub_n]^(n+1) = 0 for n=0,1,2,....

Inverse shifted Lah matrix = LM(-1) = exp(-T)

Umbrally shifted Lah[b(.)] = exp(b(.)*T) = [ binomial(n+1,k+1)*(n)!/(k)! * b(n-k) ]

A(j) = T^j / j! equals the matrix [binomial(n+1,k+1)*(n)!/(k)! * delta(n-k-j)] where delta(n) = 1 if n=0 and vanishes otherwise (Kronecker delta); i.e. A(j) is a matrix with all the terms 0 except for the j-th lower (or main for j=0) diagonal which equals that of the Lah matrix. Hence the A(j)'s form a linearly independent basis for all matrices of the form [binomial(n+1,k+1) * (n)! / (k)! * d(n-k)].

For sequences with b(0) = 1, umbrally,

LM[b(.)] = exp(b(.)*T) = [ bin(n+1,k+1)*(n)!/(k)! * b(n-k) ] .

[LM[b(.)]]^(-1) = exp(c(.)*T) = [ bin(n+1,k+1)*(n)!/(k)! * c(n-k) ] where c = LPT(b) with LPT the list partition transform of A133314. Or,

[LM[b(.)]]^(-1) = exp[LPT(b(.))*T] = LPT[LM(b(.))] = LM[LPT(b(.))] = LM[c(.)] .

The matrix operation b = T*a can be characterized in several ways in terms of the coefficients a(n) and b(n), their o.g.f.'s A(x) and B(x), or e.g.f.'s EA(x) and EB(x).

1) b(0) = 0, b(n) = (n+1)*(n) * a(n-1),

2) B(x) = x * D^2 * x^2 A(x)

3) B(x) = x * 2 *Lag(2,-:xD:,0) A(x)

4) EB(x) = D * x^2 EA(x)

where D is the derivative w.r.t. x, (:xD:)^j = x^j*D^j and Lag(n,x,m) is the associated Laguerre polynomial of order m.

The exponentiated operator can be characterized (with loose notation) as

5) exp(t*T) * a = LM(t) * a = [sum(k=0,...,n) bin(n+1,k+1) * n!/k! t^(n-k) * a(k)] = [ t^n * n! * Lag(n,-a(.)/t,1) ], a vector array.

With t=1 and a(k) = (-x)^k, then LM(1) * a = [ n! * Laguerre(n,x,1) ], a vector array with index n .

6) exp(t*T) EA(x) = EB(x) = EA[ x / (1-x*t) ] / (1-x*t)^2