

A133314


Coefficients of list partition transform: reciprocal of an exponential generating function (e.g.f.).


67



1, 1, 1, 2, 1, 6, 6, 1, 8, 6, 36, 24, 1, 10, 20, 60, 90, 240, 120, 1, 12, 30, 90, 20, 360, 480, 90, 1080, 1800, 720, 1, 14, 42, 126, 70, 630, 840, 420, 630, 5040, 4200, 2520, 12600, 15120, 5040, 1, 16, 56, 168, 112, 1008, 1344, 70
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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,
exp(a(.)*x)*exp(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(nj); which is conditionally selfinverse, 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 multipied by a(n), i.e., A(n,k) = binomial(n,k)*a(nk).
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!/(mn)! and b(n) = (m1+n)!/(m1)! 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] = Identity matrix because (a(.)+b(.))^n = delta(n), the Kronecker delta.
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 diagonally multiplying any of the fundamental matrices by a(.), followed by matrix inversion and then extraction of the b(.) 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(.) are given by diagonally multiplying the fundamental matrices by b(.).
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(m2)*t(m1), t(1)*t(2)...t(m1)*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 > n1) 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(.), as in the Pascal matrix example above and their inverses by diagonal multiplication by LPT(a) = b.
Weightedmappings interpretation for the top partition equation:
Given n prenodes (Pre) and k postnodes (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


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..250
M. Aguiar and F. Ardila, The algebraic and combinatorial structure of generalized permutahedra, MSRI Summer School July 19, 2017.
M. Aguiar and F. Ardila, Hopf monoids and generalized permutahedra, arXiv:1709.07504 [math.CO], p. 5, 2017.
N. ArkaniHamed, Y. Bai, S. He, and G. Yan, Scattering forms and the positive geometry of kinematics, color, and the worldsheet , arXiv:1711.09102 [hepth], 2017.
J. Bergström and S. Minabe, On the cohomology of the LosevManin moduli space, arXiv:1108.0338 [math.AG], (cf. p. 1), 2013.
L. Berry, S. Forcey, M. Ronco, and P. Showers, Polytopes and Hopf algebras of painted trees: Fan graphs and Stellohedra, arXiv:1608.08546 [math.CO], 2018.
T. Copeland, Bijective mapping between face polytopes of permutohedra and partitions of integers, Math StackExchange question, 2016.
T. Copeland, In the Realm of Shadows: Umbral inverses and associahedra, noncrossing partitions, symmetric polynomials, and similarity transforms, 2019.
K. Crisman, The Borda Count, the Kemeny Rule, and the permutahedron, 2014.
R. Da Rosa, D. Jensen, and D. Ranganathan, Toric graph associahedra and compactifications of M_(0,n), arXiv:1411.0537 [math.AG], 2015.
S. Forcey, The Hedra Zoo
X. Gao, S. He, Y. Zhan, Labelled tree graphs, Feynman diagrams and disk integrals , arXiv:1708.08701 [hepth], 2017.
D. Karp, D. Ranganathan, P. Riggins, and U. Whitcher, Toric Symmetry of CP^3, arXiv:1109.5157 [math.AG], 2011.
M. Lin, Graph Cohomology, 2016.
J. Loday, The Multiple Facets of the Associahedron
V. Pilaud, The Associahedron and its Friends, presentation for Séminaire Lotharingien de Combinatoire, April 4  6, 2016.
A. Postnikov, Positive Grassmannian and Polyhedral Subdivisions, arXiv:1806.05307 [math.CO], (cf. p. 17), 2018.
D. Ranganathan, GromovWitten Theory of Blowups of Toric Threefolds, senior thesis, Harvey Mudd College, 2012.
D. Ranganathan, GromovWitten Theory of Blowups of Toric Threefolds (poster), poster for senior thesis, Harvey Mudd College, 2012.


FORMULA

b(n1) = (1/n)(d/da(1))p_n[a(1),a(2),...,a(n)] where p_n are the row partition polynomials of the cumulant generator A127671.  Tom Copeland, Oct 13 2012
(E.g.f. of matrix B) = (e.g.f. of b)·exp(x·t) = exp(b(.)·t)·exp(x·t) = exp(x·t)/exp(a(·)·t) = (e.g.f. of A^(1)) and (e.g.f. of matrix A) = exp(a(·)·t)·exp(x·t) = exp(x·t)/exp(b(·)·t) = (e.g.f. of B^(1)). These e.g.f. define Appell sequences of polynomials.  Tom Copeland, Mar 22 2014
Sum of the nth row is (1)^n.  Peter Luschny, Sep 18 2015
The unsigned coefficients for the partitions a(2)*a(1)^n for n >= 0 are the Lah numbers A001286.  Tom Copeland, Aug 06 2016
G.f.: 1 / (1 + Sum_{n > 0} a(n)*x^n/n!) = 1 / exp(a.x).  Tom Copeland, Oct 18 2016
Let a(1) = 1 + x + B(1) = x + 1/2 and a(n) = B(n) = (B.)^n, where B(n) are the Bernoulli numbers defined by e^(B.t) = t / (e^t1), then t / e^(a.t) = t / [(x + 1) * t + exp(B.t)] = (e^t  1) /[ 1 + (x + 1) (e^t  1)] = exp(p.(x)t), where (p.(x))^n = p_n(x) are the shifted signed polynomials of A019538: p_0(x) = 0, p_1(x) = 1, p_2(x) = (1 + 2 x), p_3(x) = 1 + 6 x + 6 x^2, ... , p_n(x) = n * b(n1).  Tom Copeland, Oct 18 2016
With a(n) = 1/(n+1), b(n) = B(n), the Bernoulli numbers.  Tom Copeland, Nov 08 2016


EXAMPLE

Table starts:
[ 1]
[1]
[1, 2]
[1, 6, 6]
[1, 8, 6, 36, 24]
[1, 10, 20, 60, 90, 240, 120]
[1, 12, 30, 90, 20, 360, 480, 90, 1080, 1800, 720]



MATHEMATICA

Clear[a, b]; b[0] = 1; b[n_] := b[n] = Sum[Binomial[n, j]*a[j]*b[nj], {j, 1, n}]; row[0] = {1}; row[n_] := Coefficient[b[n], #]& /@ (Times @@ (a /@ #)&) /@ IntegerPartitions[n]; Table[row[n], {n, 0, 8}] // Flatten (* JeanFrançois Alcover, Apr 23 2014 *)


PROG

(Sage)
def A133314_row(n): return [(1)^len(s)*factorial(len(s))*SetPartitions(sum(s), s).cardinality() for s in Partitions(n)]
for n in (0..10): print A133314_row(n) # Peter Luschny, Sep 18 2015


CROSSREFS

Row lengths in A000041.
Cf. A000110, A000129, A000262, A000587, A000670, A001286, A007318, A019538, A049019, A084358, A094587, A105278, A110327, A110330, A128229, A132440, A132681, A132710, A263633.
Sequence in context: A048998 A213615 A049019 * A208909 A229565 A259477
Adjacent sequences: A133311 A133312 A133313 * A133315 A133316 A133317


KEYWORD

sign,tabf


AUTHOR

Tom Copeland, Oct 18 2007, Oct 29 2007, Nov 16 2007


EXTENSIONS

More terms from JeanFrançois Alcover, Apr 23 2014


STATUS

approved



