cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

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

Original entry on oeis.org

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
Offset: 0

Views

Author

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

Keywords

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, 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

Examples

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

Links

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.
Cf. A134685, A145271, A356144, A356145.

Programs

  • Mathematica
    b[0] = 1; b[n_] := b[n] = -Sum[Binomial[n, j]*a[j]*b[n-j], {j, 1, n}];
row[0] = {1}; row[n_] := Coefficient[b[n], #]& /@ (Times @@ (a /@ #)&) /@ IntegerPartitions[n];
Table[row[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Apr 23 2014 *)
  • 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

Formula

b_{n-1} = (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(xt) = exp(b.t)·exp(xt) = exp(xt)/exp(a.t) = (e.g.f. of A^(-1)) and (e.g.f. of matrix A) = exp(a.t)·exp(xt) = exp(xt)/exp(b.t) = (e.g.f. of B^(-1)), where the umbral evaluation of exp(b.t) = Sum{n >= 0} (b.t)^n / n! = Sum_{n >= 0} b_n t^n / n! is understood in the denominator. These e.g.f.s define Appell sequences of polynomials. - Tom Copeland, Mar 22 2014
Sum of the n-th 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^t-1), 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_{n-1}. - Tom Copeland, Oct 18 2016
With a_n = 1/(n+1), b_n = B_n, the Bernoulli numbers. - Tom Copeland, Nov 08 2016
Indeterminate substitutions as illustrated in A356145 lead to [E] = [L][P] = [P][E]^(-1)[P] = [P][RT] and [E]^(-1) = [P][L] = [P][E][P] = [RT][P], where [E] contains the refined Eulerian partition polynomials of A145271; [E]^(-1), A356145, the inverse set to [E]; [P], the permutohedra polynomials of this entry; [L], the classic Lagrange inversion polynomials of A134685; and [RT], the reciprocal tangent polynomials of A356144. Since [L]^2 = [P]^2 = [RT]^2 = [I], the substitutional identity, [L] = [E][P] = [P][E]^(-1) = [RT][P], [RT] = [E]^(-1)[P] = [P][L][P] = [P][E], and [P] = [L][E] = [E][RT] = [E]^(-1)[L] = [RT][E]^(-1). - Tom Copeland, Oct 05 2022

Extensions

More terms from Jean-François Alcover, Apr 23 2014

A145271 Coefficients for expansion of (g(x)d/dx)^n g(x); refined Eulerian numbers for calculating compositional inverse of h(x) = (d/dx)^(-1) 1/g(x); iterated derivatives as infinitesimal generators of flows.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 11, 4, 7, 1, 1, 26, 34, 32, 15, 11, 1, 1, 57, 180, 122, 34, 192, 76, 15, 26, 16, 1, 1, 120, 768, 423, 496, 1494, 426, 294, 267, 474, 156, 56, 42, 22, 1, 1, 247, 2904, 1389, 4288, 9204, 2127, 496, 5946, 2829, 5142, 1206, 855, 768, 1344, 1038, 288, 56, 98, 64, 29, 1
Offset: 0

Views

Author

Tom Copeland, Oct 06 2008

Keywords

Comments

For more detail, including connections to Legendre transformations, rooted trees, A139605, A139002 and A074060, see Mathemagical Forests p. 9.
For connections to the h-polynomials associated to the refined f-polynomials of permutohedra see my comments in A008292 and A049019.
From Tom Copeland, Oct 14 2011: (Start)
Given analytic functions F(x) and FI(x) such that F(FI(x))=FI(F(x))=x about 0, i.e., they are compositional inverses of each other, then, with g(x) = 1/dFI(x)/dx, a flow function W(s,x) can be defined with the following relations:
W(s,x) = exp(s g(x)d/dx)x = F(s+FI(x)) ,
W(s,0) = F(s) ,
W(0,x) = x ,
dW(0,x)/ds = g(x) = F'[FI(x)] , implying
dW(0,F(x))/ds = g(F(x)) = F'(x) , and
W(s,W(r,x)) = F(s+FI(F(r+FI(x)))) = F(s+r+FI(x)) = W(s+r,x) . (See MF link below.) (End)
dW(s,x)/ds - g(x)dW(s,x)/dx = 0, so (1,-g(x)) are the components of a vector orthogonal to the gradient of W and, therefore, tangent to the contour of W, at (s,x) . - Tom Copeland, Oct 26 2011
Though A139605 contains A145271, the op. of A145271 contains that of A139605 in the sense that exp(s g(x)d/dx) w(x) = w(F(s+FI(x))) = exp((exp(s g(x)d/dx)x)d/du)w(u) evaluated at u=0. This is reflected in the fact that the forest of rooted trees assoc. to (g(x)d/dx)^n, FOR_n, can be generated by removing the single trunk of the planted rooted trees of FOR_(n+1). - Tom Copeland, Nov 29 2011
Related to formal group laws for elliptic curves (see Hoffman). - Tom Copeland, Feb 24 2012
The functional equation W(s,x) = F(s+FI(x)), or a restriction of it, is sometimes called the Abel equation or Abel's functional equation (see Houzel and Wikipedia) and is related to Schröder's functional equation and Koenigs functions for compositional iterates (Alexander, Goryainov and Kudryavtseva). - Tom Copeland, Apr 04 2012
g(W(s,x)) = F'(s + FI(x)) = dW(s,x)/ds = g(x) dW(s,x)/dx, connecting the operators here to presentations of the Koenigs / Königs function and Loewner / Löwner evolution equations of the Contreras et al. papers. - Tom Copeland, Jun 03 2018
The autonomous differential equation above also appears with a change in variable of the form x = log(u) in the renormalization group equation, or Beta function. See Wikipedia, Zinn-Justin equations 2.10 and 3.11, and Krajewski and Martinetti equation 21. - Tom Copeland, Jul 23 2020
A variant of these partition polynomials appears on p. 83 of Petreolle et al. with the indeterminates e_n there related to those given in the examples below by e_n = n!*(n'). The coefficients are interpreted as enumerating certain types of trees. See also A190015. - Tom Copeland, Oct 03 2022

Examples

			From _Tom Copeland_, Sep 19 2014: (Start)
Let h(x) = log((1+a*x)/(1+b*x))/(a-b); then, g(x) = 1/(dh(x)/dx) = (1+ax)(1+bx), so (0')=1, (1')=a+b, (2')=2ab, evaluated at x=0, and higher order derivatives of g(x) vanish. Therefore, evaluated at x=0,
R^0 g(x) =  1
R^1 g(x) =  a+b
R^2 g(x) = (a+b)^2 + 2ab = a^2 + 4 ab + b^2
R^3 g(x) = (a+b)^3 + 4*(a+b)*2ab = a^3 + 11 a^2*b + 11 ab^2 + b^3
R^4 g(x) = (a+b)^4 + 11*(a+b)^2*2ab + 4*(2ab)^2
         =  a^4 + 26 a^3*b + 66 a^2*b^2 + 26 ab^3 + b^4,
etc., and these bivariate Eulerian polynomials (A008292) are the first few coefficients of h^(-1)(x) = (e^(ax) - e^(bx))/(a*e^(bx) - b*e^(ax)), the inverse of h(x). (End)
Triangle starts:
  1;
  1;
  1,   1;
  1,   4,    1;
  1,  11,    4,    7,    1;
  1,  26,   34,   32,   15,   11,    1;
  1,  57,  180,  122,   34,  192,   76,  15,   26,   16,    1;
  1, 120,  768,  423,  496, 1494,  426, 294,  267,  474,  156,   56,  42,  22,    1;
  1, 247, 2904, 1389, 4288, 9204, 2127, 496, 5946, 2829, 5142, 1206, 855, 768, 1344, 1038, 288, 56, 98, 64, 29, 1;

References

  • D. S. Alexander, A History of Complex Dynamics: From Schröder to Fatou to Julia, Friedrich Vieweg & Sohn, 1994.
  • T. Mansour and M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, Chapman and Hall/CRC, 2015.

Links

Crossrefs

Cf. (A133437, A086810, A181289) = (LIF, reduced LIF, associated g(x)), where LIF is a Lagrange inversion formula. Similarly for (A134264, A001263, A119900), (A134685, A134991, A019538), (A133932, A111999, A007318).
Cf. A008292, A049019, A074060, A129185, A139002, A139605, A190015.
Second column is A000295, subdiagonal is A000124, row sums are A000142, row lengths are A000041. - Peter Luschny, Jul 21 2016
Cf. A036039, A133314, A356144, A356145.

Programs

  • Maple
    with(LinearAlgebra): with(ListTools):
A145271_row := proc(n) local b, M, V, U, G, R, T;
if n < 2 then return 1 fi;
b := (n,k) -> `if`(k=1 or k>n+1,0,binomial(n-1,k-2)*g[n-k+1]);
M := n -> Matrix(n, b):
V := n -> Vector[row]([1, seq(0,i=2..n)]):
U := n -> VectorMatrixMultiply(V(n), M(n)^(n-1)):
G := n -> Vector([seq(g[i], i=0..n-1)]);
R := n -> VectorMatrixMultiply(U(n), G(n)):
T := Reverse([op(sort(expand(R(n+1))))]);
seq(subs({seq(g[i]=1, i=0..n)},T[j]),j=1..nops(T)) end:
for n from 0 to 9 do A145271_row(n) od; # Peter Luschny, Jul 20 2016

Formula

Let R = g(x)d/dx; then
R^0 g(x) = 1 (0')^1
R^1 g(x) = 1 (0')^1 (1')^1
R^2 g(x) = 1 (0')^1 (1')^2 + 1 (0')^2 (2')^1
R^3 g(x) = 1 (0')^1 (1')^3 + 4 (0')^2 (1')^1 (2')^1 + 1 (0')^3 (3')^1
R^4 g(x) = 1 (0')^1 (1')^4 + 11 (0')^2 (1')^2 (2')^1 + 4 (0')^3 (2')^2 + 7 (0')^3 (1')^1 (3')^1 + 1 (0')^4 (4')^1
R^5 g(x) = 1 (0') (1')^5 + 26 (0')^2 (1')^3 (2') + (0')^3 [34 (1') (2')^2 + 32 (1')^2 (3')] + (0')^4 [ 15 (2') (3') + 11 (1') (4')] + (0')^5 (5')
R^6 g(x) = 1 (0') (1')^6 + 57 (0')^2 (1')^4 (2') + (0')^3 [180 (1')^2 (2')^2 + 122 (1')^3 (3')] + (0')^4 [ 34 (2')^3 + 192 (1') (2') (3') + 76 (1')^2 (4')] + (0')^5 [15 (3')^2 + 26 (2') (4') + 16 (1') (5')] + (0')^6 (6')
where (j')^k = ((d/dx)^j g(x))^k. And R^(n-1) g(x) evaluated at x=0 is the n-th Taylor series coefficient of the compositional inverse of h(x) = (d/dx)^(-1) 1/g(x), with the integral from 0 to x.
The partitions are in reverse order to those in Abramowitz and Stegun p. 831. Summing over coefficients with like powers of (0') gives A008292.
Confer A190015 for another way to compute numbers for the array for each partition. - Tom Copeland, Oct 17 2014
Equivalent matrix computation: Multiply the n-th diagonal (with n=0 the main diagonal) of the lower triangular Pascal matrix by g_n = (d/dx)^n g(x) to obtain the matrix VP with VP(n,k) = binomial(n,k) g_(n-k). Then R^n g(x) = (1, 0, 0, 0, ...) [VP * S]^n (g_0, g_1, g_2, ...)^T, where S is the shift matrix A129185, representing differentiation in the divided powers basis x^n/n!. - Tom Copeland, Feb 10 2016 (An evaluation removed by author on Jul 19 2016. Cf. A139605 and A134685.)
Also, R^n g(x) = (1, 0, 0, 0, ...) [VP * S]^(n+1) (0, 1, 0, ...)^T in agreement with A139605. - Tom Copeland, Jul 21 2016
A recursion relation for computing each partition polynomial of this entry from the lower order polynomials and the coefficients of the cycle index polynomials of A036039 is presented in the blog entry "Formal group laws and binomial Sheffer sequences". - Tom Copeland, Feb 06 2018
A formula for computing the polynomials of each row of this matrix is presented as T_{n,1} on p. 196 of the Ihara reference in A139605. - Tom Copeland, Mar 25 2020
Indeterminate substitutions as illustrated in A356145 lead to [E] = [L][P] = [P][E]^(-1)[P] = [P][RT] and [E]^(-1) = [P][L] = [P][E][P] = [RT][P], where [E] contains the refined Eulerian partition polynomials of this entry; [E]^(-1), A356145, the inverse set to [E]; [P], the permutahedra polynomials of A133314; [L], the classic Lagrange inversion polynomials of A134685; and [RT], the reciprocal tangent polynomials of A356144. Since [L]^2 = [P]^2 = [RT]^2 = [I], the substitutional identity, [L] = [E][P] = [P][E]^(-1) = [RT][P], [RT] = [E]^(-1)[P] = [P][L][P] = [P][E], and [P] = [L][E] = [E][RT] = [E]^(-1)[L] = [RT][E]^(-1). - Tom Copeland, Oct 05 2022

Extensions

Title amplified by Tom Copeland, Mar 17 2014
R^5 and R^6 formulas and terms a(19)-a(29) added by Tom Copeland, Jul 11 2016
More terms from Peter Luschny, Jul 20 2016

A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 1, 11, 25, 15, 1, 26, 130, 210, 105, 1, 57, 546, 1750, 2205, 945, 1, 120, 2037, 11368, 26775, 27720, 10395, 1, 247, 7071, 63805, 247555, 460845, 405405, 135135, 1, 502, 23436, 325930, 1939630, 5735730, 8828820, 6756750, 2027025, 1
Offset: 0

Views

Author

Wolfdieter Lang, Oct 14 2005

Keywords

Comments

Previous name was: Coefficient triangle of polynomials used for e.g.f.s of Stirling2 diagonals.
For the o.g.f. of diagonal k of the Stirling2 triangle one has a similar result. See A008517 (second-order Eulerian triangle).
A(m,x), the o.g.f. for column m, satisfies the recurrence A(m,x) = x*(x*(d/dx)A(m-1,x) + m*A(m-1,x))/(1-(m+1)*x), for m >= 1 and A(0,x) = 1/(1-x).
The e.g.f. for the sequence in column k+1, k >= 0, of A008278, i.e., for the diagonal k >= 0 of the Stirling2 triangle A048993, is exp(x)*Sum_{m=0..k} a(k,m)*(x^(m+k))/(m+k)!.
It appears that the triangles in this sequence and A124324 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
A refined version of this triangle is given in A356145, which contains a link providing the precise relationship between A124324 and this entry, confirming Jörgen Backelin's observation above. - Tom Copeland, Sep 24 2022

Examples

			Triangle starts:
  [1]
  [1, 1]
  [1, 4,  3]
  [1, 11, 25,  15]
  [1, 26, 130, 210,  105]
  [1, 57, 546, 1750, 2205, 945]
  ...
The e.g.f. of [0,0,1,7,25,65,...], the k=3 column of A008278, but with offset n=0, is exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!).
Third row [1,4,3]: There are three plane increasing trees on 3 vertices. The number of colors are shown to the right of a vertex.
...................................................
....1o.(1+t)...........1o.t*(1+t).....1o.t*(1+t)...
....|................. /.\............/.\..........
....|................ /...\........../...\.........
....2o.(1+t)........2o.....3o......3o....2o........
....|..............................................
....|..............................................
....3o.............................................
...................................................
The total number of trees is (1+t)^2 + t*(1+t) + t*(1+t) = 1+4*t+3*t^2 = R(2,t).

Links

Crossrefs

Row sums give A006351(k+1), k>=0.
The column sequences start with A000012 (powers of 1), A000295 (Eulerian numbers), A112495, A112496, A112497.
Cf. A008278, A008517, A048993, A054589, A075856, A134991, A201637, A124324.
Antidiagonal sums give A000110.
Cf. A356145.

Programs

  • Maple
    T := (n, k) -> add(combinat:-eulerian2(n, j)*binomial(n-j, n-k), j=0..n):
seq(seq(T(n, k), k=0..n), n=0..9); # Peter Luschny, Apr 11 2016
  • Mathematica
    max = 11; f[x_, t_] := -1 - (1 + t)/t*ProductLog[-t/(1 + t)*Exp[(x - t)/(1 + t)]]; coes = CoefficientList[ Series[f[x, t], {x, 0, max}, {t, 0, max}], {x, t}]* Range[0, max]!; Table[coes[[n, k]], {n, 0, max}, {k, 1, n - 1}] // Flatten (* Jean-François Alcover, Nov 22 2012, from e.g.f. *)

Formula

a(k, m) = 0 if k < m, a(k, -1):=0, a(0, 0)=1, a(k, m)=(m+1)*a(k-1, m) + (k+m-1)*a(k-1, m-1) else.
From Peter Bala, Sep 30 2011: (Start)
E.g.f.: A(x,t) = -1-((1+t)/t)*LambertW(-(t/(1+t))*exp((x-t)/(1+t))) = x + (1+t)*x^2/2! + (1+4*t+3*t^2)*x^3/3! + .... A(x,t) is the inverse function of (1+t)*log(1+x)-t*x.
A(x,t) satisfies the partial differential equation (1-x*t)*dA/dx = 1 + A + t*(1+t)*dA/dt. It follows that the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) =(n*t+1)*R(n,t) + t*(1+t)*dR(n,t)/dt. Cf. A054589 and A075856. The polynomials t/(1+t)*R(n,t) are the row polynomials of A134991.
The generating function A(x,t) satisfies the autonomous differential equation dA/dx = (1+A)/(1-t*A). Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees on n+1 vertices where the non-leaf vertices of outdegree k come in t^(k-1)*(1+t) colors. An example is given below. Cf. A006351, which corresponds to the case t = 1. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x) = (1+x)/(1-x*t). Then R(n,t) = (f(x)*d/dx)^n(f(x)) evaluated at x = 0. (End)
Sum_{j=0..n} T(n-j,j) = A000110(n). - Alois P. Heinz, Jun 20 2022
From Mikhail Kurkov, Apr 01 2025: (Start)
E.g.f.: B(y) = -w/(x*(1+w)) where w = LambertW(-x/(1+x)*exp((y-x)/(1+x))) satisfies the first-order ordinary differential equation (1+x)*B'(y) = B(y)*(1+x*B(y))^2, hence row polynomials are P(n,x) = P(n-1,x) + x*Sum_{j=0..n-1} binomial(n, j)*P(j,x)*P(n-j-1,x) for n > 0 with P(0,x) = 1 (see MathOverflow link).
Conjecture: row polynomials are P(n,x) = Sum_{i=0..n} Sum_{j=0..i} Sum_{k=0..j} (n+i)!*Stirling1(n+j-k,j-k)*x^k*(x+1)^(j-k)*(-1)^(j+k)/((n+j-k)!*(i-j)!*k!). (End)
Conjecture: g.f. satisfies 1/(1 - x - x*y/(1 - 2*x - 2*x*y/(1 - 3*x - 3*x*y/(1 - 4*x - 4*x*y/(1 - 5*x - 5*x*y/(1 - ...)))))) (see A383019 for conjectures about combinatorial interpretation and algorithm for efficient computing). - Mikhail Kurkov, Apr 21 2025

Extensions

New name from Peter Luschny, Apr 11 2016

A307804 Triangle T(n,k) read by rows: number of labeled 2-regular digraphs (multiple arcs and loops allowed) on n nodes with k components.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 14, 6, 1, 0, 201, 68, 12, 1, 0, 4704, 1285, 200, 20, 1, 0, 160890, 36214, 4815, 460, 30, 1, 0, 7538040, 1422288, 160594, 13755, 910, 42, 1, 0, 462869190, 74416131, 7151984, 535864, 33110, 1624, 56, 1, 0, 36055948320, 5016901734, 413347787, 26821368, 1490664, 70686, 2688, 72, 1
Offset: 0

Views

Author

R. J. Mathar, Apr 29 2019

Keywords

Examples

			Triangle T(n,k) starts:
  1;
  0,       1;
  0,       2,       1;
  0,      14,       6,      1;
  0,     201,      68,     12,     1;
  0,    4704,    1285,    200,    20,   1;
  0,  160890,   36214,   4815,   460,  30,  1;
  0, 7538040, 1422288, 160594, 13755, 910, 42, 1;
  ...

Links

Crossrefs

Cf. A123543 (column k=1), A000681 (row sums).

Programs

  • Maple
    b:= proc(n) option remember; `if`(n<2, 1,
      n^2*b(n-1)-n*(n-1)^2*b(n-2)/2)
    end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)-
      add(j*binomial(n, j)*b(n-j)*a(j), j=1..n-1)/n)
    end:
g:= proc(n, k) option remember; `if`(n=0, x^k/k!,
      add(g(n-j, k+1)*a(j)*binomial(n,j), j=1..n))
    end:
T:= (n,k)-> coeff(g(n, 0), x, k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Mar 22 2025
  • Mathematica
    b[n_] := b[n] = If[n < 2, 1, n^2*b[n - 1] - n*(n - 1)^2*b[n - 2]/2];
a[n_] := a[n] = If[n == 0, 0, b[n] - Sum[j*Binomial[n, j]*b[n - j]*a[j], {j, 1, n - 1}]/n];
g[n_, k_] := g[n, k] = If[n == 0, x^k/k!, Sum[g[n - j, k + 1]*a[j]* Binomial[n, j], {j, 1, n}]];
T[n_, k_] := Coefficient[g[n, 0], x, k];
Table[Table[T[n, k], { k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 16 2025, after Alois P. Heinz *)

Formula

T(n,1) = A123543(n).
T(n,k) = Sum_{Compositions n=n_1+n_2+...n_k, n_i>=1} multinomial(n; n_1,n_2,..,n_k) * T(n_1,1) * T(n_2,1)*... *T(n_k,1)/ k!.
E.g.f.: Sum_{n,k>=0} T(n,k)*x^n*t^k/n! = exp(t*E123543(x)) where E123543(x) = Sum_{n>=1} A123543(n)*x^n/t^n. [Gilbert]. - R. J. Mathar, May 08 2019
Conjectures from Mikhail Kurkov, Mar 22 2025: (Start)
Recursion for the k-th column (independently of other columns): T(n,k) = (1/(n-k))*Sum_{j=2..n-k+1} c(j-1)*binomial(n,j)*T(n-j+1,k) for 1 <= k < n with T(n,n) = 1 where b(n) = A123543(n), c(n) = n*b(n+1) - Sum_{j=1..n-1} binomial(n+1,j+1)*b(n-j+1)*c(j) for n > 0.
Production matrix is binomial(n,k)*d(n-k) (starting from the first row) for 0 <= k <= n, 0 otherwise where d(n) = E_n^{(-1)} from A356145 with a_k = b(k+1) for k > 0 (see Tom Copeland link).
The same things seems to work for any b(n) with b(1) = 1 (I mean that it works for e.g.f. exp(t*F(x)) where F(x) = Sum_{n>=1} b(n)*x^n/n!). (End)

A356144 Coefficients of the set of partition polynomials [RT] = [P][E]; i.e., coefficients of polynomials resulting from using the set of refined Eulerian polynomials, [E], of A145271 as the indeterminates of the set of permutahedra polynomials, [P], of A133314. Irregular triangle read by rows with lengths given by A000041.

Original entry on oeis.org

1, -1, 1, -1, -1, 2, -1, 1, -3, 2, 1, -1, -1, 4, -4, -2, 5, -1, -1, 1, -5, 8, 2, -4, -2, -4, 5, 4, -4, -1, -1, 6, -12, -3, 8, 18, -6, -14, 13, 2, -16, 14, 0, -8, -1, 1, -7, 18, 3, -20, 0, -15, 8, 18, 57, 6, -54, -15, -12, 84, -30, -48, 14, 14, -8, -13, -1, -1, 8, -24, -4, 32, 51, -27, -16, -6, 171, -42, -177, 50, 90, -18, 456, -276, -246, -15, 30, 154, -42, 124, -166, -113, 42, 6, -21, -19, -1
Offset: 0

Views

Author

Tom Copeland, Jul 27 2022

Keywords

Comments

I stipulate that the row lengths are A000041, but this imposes the insertion of a zero as a coefficient of a monomial for the polynomial RT_7 and for RT_8. The number of nonzero coefficients in each higher order polynomial remains to be determined. The monomials of the partition polynomials are arranged in the order (bottom to top) in Abramowitz and Stegun (starting on p. 831, link in A000041).
The analytic interpretation of these coefficients is related to the e.g.f.s of reciprocals of the derivatives (slopes of tangents) of a pair of compositionally inverse e.g.f.s as explicitly shown in the formulas.
With the notation introduced in the formula section, this set of partition polynomials, [RT], is the e.g.f. counterpart to the special Schur expansion coefficients [b], or [K], of A355201 for o.g.f.s. and is conjugate dual to the Lagrange inversion polynomials [L] of A134685.
For example, as shown in the formulas, [RT] = [P][E] = [P][L][P] where [P] is the set of polynomials of A133314, the refined Euler characteristic polynomials of the permutahedra; [E], the set A145271, the refined Eulerian polynomials; and [L], the set A134685, the classic Lagrange inversion polynomials--all related to transformations of e.g.f.s, or Taylor series, for which [RT], [L], and [E] can each be used to give the compositional inverse and [P], the multiplicative inverse, or reciprocal.
On the other hand, as shown in formulas for A355201, [K] = [R][N] = [R][A][R] where [R] is the set A263633 (mod signs), refined Pascal polynomials; [N], the set A134264, the refined Narayana, or noncrossing partition, polynomials; and [A], the set A133437, the refined Euler characteristic polynomials of the associahedra--all related to transformations of o.g.f.s, or power series, for which [K], [A], and [N] can each be used to give the compositional inverse and [R], the multiplicative inverse, or reciprocal. This is related to three pairs of compositionally inverse series--two pairs of Laurent series and one pair of power series.

Examples

			Arranged by rows, the coefficients are
0)  1;
1) -1;
2)  1, -1;
3) -1, 2, -1;
4)  1, -3, 2, 1, -1;
5) -1, 4, -4, -2, 5, -1, -1;
6)  1, -5, 8, 2, -4, -2, -4, 5, 4, -4, -1;
7) -1, 6, -12, -3, 8, 18, -6, -14, 13, 2, -16, 14, 0, -8, -1;
8)  1, -7, 18, 3, -20, 0, -15, 8, 18, 57, 6, -54, -15, -12, 84, -30, -48, 14, 14, -8, -13, -1;
. . .
The first few partition polynomials are
RT_0 =  1,
RT_1 = -a1,
RT_2 = a1^2  - a2,
RT_3 = -a1^3 + 2 a1 a2 - a3,
Rt_4 = a1^4 - 3 a1^2 a2 + 2 a2^2 + a1 a3 - a4,
RT_5 = -a1^5 + 4 a1^3 a2 - 4 a1 a2^2 - 2 a1^2 a3 + 5 a2 a3 - a1 a4 - a5,
RT_6 = a1^6 - 5 a1^4 a2 + 8 a1^2 a2^2 + 2 a1^3 a3 - 4 a2^3 - 2 a1 a2 a3 - 4 a1^2 a4 + 5 a3^2 + 4 a2 a4 - 4 a1 a5 - a6,
RT_7 = -a1^7 + 6 a1^5 a2 - 12*a1^3 a2^2 - 3 a1^4 a3 + 8 a1 a2^3 + 18 a1^2 a2 a3 - 6 a1^3 a4 - 14 a2^2 a3 + 13 a1 a3^2 + 2 a1 a2 a4 - 16 a1^2 a5 + 14 a3 a4 + 0 a2 a5 - 8 a1 a6 - a7,
RT_8 =  a1^8 - 7 a1^6 a2 + 18 a1^4 a2^2 + 3 a1^5 a3 - 20 a1^2 a2^3 + 0 a1^3 a2 a3 - 15 a1^4 a4 + 8 a2^4 + 18 a1 a2^2 a3 + 57 a1^2 a3^2 + 6 a1^2 a2 a4 - 54 a1^3 a5 - 15 a2 a3^2 - 12 a2^2 a4 + 84 a1 a3 a4 - 30 a1 a2 a5 - 48 a1^2 a6 + 14 a4^2 + 14 a3 a5 - 8 a2 a6 - 13 a1 a7 - a8.

Links

Crossrefs

Cf. A000108, A133314, A133437, A134685, A145271, A263633, A355201, A356145.

Programs

  • Mathematica
    rows[nn_] := {{1}}~Join~With[{s = 1 / D[InverseSeries[Integrate[1/(1 + Sum[c[k] x^k/k!, {k, nn}] + O[x]^(nn+1)), x]], x]}, Table[Coefficient[n! s, x^n Product[c[t], {t, p}]], {n, nn}, {p, Reverse[Sort[Sort /@ IntegerPartitions[n]]]}]];
rows[7] // Flatten (* Andrey Zabolotskiy, Feb 17 2024 *)
  • SageMath
    B. = PolynomialRing(ZZ)
A. = PowerSeriesRing(B)
f = 1/(1 + a1*x + a2*x^2/factorial(2) + a3*x^3/factorial(3) + a4*x^4/factorial(4) + a5*x^5/factorial(5) + a6*x^6/factorial(6) + a7*x^7/factorial(7) + a8*x^8/factorial(8) + a9*x^9/factorial(9) + a10*x^10/factorial(10) )
g = integrate(f)
h = g.reverse()
w = derivative(h,x)
I = 1 / w
# Added by # Peter Luschny, Feb 17 2024:
# The list of coefficients in sparse format (i.e. without the zeros):
for n, c in enumerate(I.list()[:10]):
    print(f"RT[{n}]", (factorial(n)*c).coefficients())

Formula

Denote this set of partition polynomials by [RT], the permutahedra polynomials of A133314 by [P], the refined Eulerian polynomials of A145271 by [E], and the Lagrange inversion polynomials of A134685 for e.g.f.s by [L]. Let the typically noncommutative product of two sets, e.g., [P][E], represent the substitution of the polynomials of [E] for the indeterminates of [P], i.e., a composition at the level of the indeterminates (see A356145 for examples). Let [I] be the substitutional identity transformation, and mark the substitutional inverse with the superscript -1. Then the following relations hold.
[RT] = [P][E] = [P][L][P] = [P]^{-1}[L][P] = [P][L][P]^{-1} since [P] is an involution, i.e., [P]^2 = [I], or [P] = [P]^{-1}, so [RT] and [L] are conjugate duals.
[RT]^{-1} = ([P][E])^{-1} = [E]^{-1}[P] = ([P][L][P])^{-1} = [P][L][P] = [RT], with [E]^{-1} = A356145, since [L] and [P] are involutions, so is [RT], i.e., [RT]^2 = [I].
RT_n(a_1,a_2,...,a_n) = D_{x=0}^n 1 / [ D_x f^{(-1)}(x)] for which D_x is the derivative w.r.t. x and the indeterminates are defined by 1 / [D_x f(x)] = 1 + a_1 x + a_2 x^2/2! + a_3 x^3/3! + ... with f(x) and f^{(-1)}(x) a compositional inverse pair of formal Taylor series, or e.g.f.s. This is the analytic equivalent of the algebraic relation [RT] = [P][E]. In words, the partition polynomials of row n (initial row is 0) is the n-th coefficient of the formal Taylor series of the reciprocal of the derivative of the compositional inverse of a function in terms of the Taylor series coefficients of the reciprocal of the derivative of that function. Note the correspondence with the analytic interpretation of [E]^{-1} of A356145, consistent with the algebraic identities above.
RT_n(a_1,a_2,...,a_n) = D_{x=0}^n f'(f^{(-1)}(x)) also, by the inverse function theorem, where the prime denotes differentiation with respect to the argument of the function.
With all a_k = (-1)^k, RT_0 = RT_1 = 1, otherwise RT_n = 0. This is determined with f(x) = e^{x}-1 and f^{(-1)}(x) = log(1+x).
With all a_k = 1, RT_0 = 1, RT_1 = -1, otherwise RT_n=0. This is determined with f(x) =1-e^{-x} and f^{(-1)}(x) = -log(1-x).
With all a_k = -1, RT_0 = 1 and RT_n = 2^(n-1) otherwise. This is determined with f(x) = (x - log(2-e^x))/2 and f^{(-1)}(x) = x - log(cosh(x)). (Careful, these are not the row sums of the absolute values of the numerical coefficients, which for the first ten polynomials are 1, 1, 2, 4, 8, 18, 40, 122, 446, and 2428.)
With a_k = k! 2^k, RT_0 = 1 and RT_n = -2*(2(n-1))! / (n-1)! = -2*n!*A000108(n-1) otherwise. This is determined with f(x) = x - x^2 and f^{(-1)}(x) = (1 - sqrt(1-4x))/2. Similar relations hold for the Fuss-Catalan sequences with f(x) = x - x^{m+1} for m > 1.

Extensions

Order of terms in rows 4-6 corrected by Andrey Zabolotskiy, Feb 17 2024
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.