cp's OEIS Frontend

Let f(t) = u(t) - u(0) = Sum_{n>=1} u_n * t^n.

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

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

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

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

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

P(5,t) = (1')^(-9) * [ 1680 (2')^4 - 2520 (1') (2')^2 (3') + 360 (1')^2 (3')^2 + 720 (1')^2 (2') (4') - 120 (1')^3 (5') ] * t^5 / 5!

P(6,t) = (1')^(-11) * [ -30240 (2')^5 + 60480 (1') (2')^3 (3') - 20160 (1')^2 (2') (3')^2 - 20160 (1')^2 (2')^2 (4') + 5040 (1')^3 (3')(4') + 5040 (1')^3 (2')(5') - 720 (1')^4 (6') ] * t^6 / 6!

P(7,t) = (1')^(-13) * [ 665280 (2')^6 - 1663200 (1')(2')^4(3') + (1')^2 [907200 (2')^2(3')^2 + 604800 (2')^3(4')] - (1')^3 [60480 (3')^3 + 362880 (2')(3')(4') + 181440 (2')^2(5')] + (1')^4 [20160 (4')^2 + 40320 (3')(5') + 40320 (2')(6')] - 5040 (1')^5(7')] * t^7 / 7!

P(8,t) = (1')^(-15) * [ -17297280 (2')^7 + 51891840 (1')(2')^5(3') - (1')^2 [39916800 (2')^3(3')^2 + 19958400 (2')^4(4')] + (1')^3 [6652800 (2')(3')^3 + 19958400 (2')^2(3')(4') + 6652800 (2')^3(5')] - (1')^4 [1814400 (3')^2(4') + 1814400 (2')(4')^2 + 3628800 (2')(3')(5') + 1814400 (2')^2(6')] + (1')^5 [362880 (4')(5') + 362880 (3')(6') + 362880 (2')(7')] - 40320 (1')^6(8')] * t^8 / 8!

...

See A134685 for more information.

A111785 is obtained from A133437 by dividing through the bracketed terms of the P(n,t) by n! and unsigned A111785 is a refinement of A033282 and A126216. - Tom Copeland, Sep 28 2008

For relation to the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see the Loday and McCammond links. E.g., P(5,t) = (1')^(-9) * [ 14 (2')^4 - 21 (1') (2')^2 (3') + 6 (1')^2 (2') (4')+ 3 (1')^2 (3')^2 - 1 (1')^3 (5') ] * t^5 is related to the 3-D associahedron with 14 vertices (0-D faces), 21 edges (1-D faces), 6 pentagons (2-D faces), 3 rectangles (2-D faces), 1 3-D polytope (3-D faces). Summing over faces of the same dimension gives A033282 or A126216. - Tom Copeland, Sep 29 2008

A relation between this Lagrange inversion for an o.g.f. and partition polynomials formed from the "refined Lah numbers" A130561 is presented in the link "Lagrange a la Lah" along with umbral binary tree representations.

With f(x,t) = x + t*Sum_{n>=2} u_n*x^n, the compositional inverse in x is related to the velocity profile of particles governed by the inviscid Burgers's, or Hopf, eqn. See A001764 and A086810. - Tom Copeland, Feb 15 2014

Newton was aware of this power series expansion for series reversion. See the Ferraro reference p. 75 eqn. 52. - Tom Copeland, Jan 22 2017

The coefficients of the partition polynomials divided by the associated factorial enumerate the faces of the convex, bounded polytopes called the associahedra, and the absolute value of the sum of the renormalized 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 either n! (unnormalized) or unity (normalized). 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 u_1 = 1 and the other u_n replaced by suitably signed partition polynomials of A263633, the partition polynomials enumerating the refined noncrossing partitions of A134264 with a shift in indices are obtained (cf. In the Realm of Shadows). - Tom Copeland, Nov 16 2019

Relations between associahedra and oriented n-simplices are presented by Halvorson and by Street. - Tom Copeland, Dec 08 2019

Let f(x;t,n) = x - t * x^(n+1), giving u_1 = (1') = 1 and u_(n+1) = (n+1) = -t. Then inverting in x with t a parameter gives 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). Comparing this with the same result in A134264 gives relations between the faces of associahedra and noncrossing partitions (and other combinatorial constructs related to these inversion formulas and those listed in A145271). - Tom Copeland, Jan 27 2020

From Tom Copeland, Mar 24 2020: (Start)

There is a mapping between the faces of K_n, the associahedron of dimension (n-1), and polygon dissections. The dissecting noncrossing diagonals (i.e., nonintersecting in the interior) form subpolygons. Assign the indeterminate x_k to a subpolygon where k = (number of vertices of the subpolygon) - 1. Multiply the x_k together to form the monomials for the inversion formula.

For the 3-dimensional associahedron K_4, the fundamental polygon is the hexagon, which can be dissected into pentagons, associated to x_4; tetragons, to x_3; and triangles, to x_2; for example, there are six distinguished partitions of the hexagon into one triangle and one pentagon, sharing two vertices, associated to the monomial 6 * x_2 * x_4 since the unshared vertex of the triangle can be moved consecutively from one vertex of the hexagon to the next. This term corresponds to 720 (1')^2 (2') (4') / 5! in P(5,t) above, denumerating the six pentagonal facets of K_4. (End)

Let f(t) = -log(1 - u(.)*t) = Sum_{n>=1} (u_n / n) * t^n.

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

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

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

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

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

P(5,t) = (1')^(-9) * [ 105 (2')^4 - 210 (1') (2')^2 (3') + 40 (1')^2 (3')^2 + 90 (1')^2 (2') (4') - 24 (1')^3 (5') ] * t^5 / 5!

P(6,t) = (1')^(-11) * [ -945 (2')^5 + 2520 (1') (2')^3 (3') - 1120 (1')^2 (2') (3')^2 - 1260 (1')^2 (2')^2 (4') + 420 (1')^3 (3')(4') + 504 (1')^3 (2')(5') - 120 (1')^4 (6') ] * t^6 / 6!

See A134685 for more information.

From Tom Copeland, Sep 28 2016: (Start)

P(7,t) = (1')^(-13) * [ 10395 (2')^6 - 34650 (1')(2')^4(3') + (1')^2 [25200 (2')^2(3')^2 + 18900 (2')^3(4')] - (1')^3 [2240 (3')^3 + 15120 (2')(3')(4') + 9072 (2')^2(5')] + (1')^4 [1260 (4')^2 + 2688 (3')(5') + 3360 (2')(6')] - 720 (1')^5(7')] * t^7 / 7!

P(8,t) = (1')^(-15) * [ -135135 (2')^7 + 540540 (1')(2')^5(3') - (1')^2 [554400 (2')^3(3')^2 + 311850 (2')^4(4')] + (1')^3 [123200 (2')(3')^3 + 415800 (2')^2(3')(4') + 166320 (2')^3(5')] - (1')^4 [50400 (3')^2(4') + 56700 (2')(4')^2 + 120960 (2')(3')(5') + 75600 (2')^2(6')] + (1')^5 [18144 (4')(5') + 20160 (3')(6') + 25920 (2')(7')] - 5040 (1')^6(8')] * t^8 / 8! (End)

The solution to Schröder's third problem.

Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).

a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022]

a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001

Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002

Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012

For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).

a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004

Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number (A008517). - Ross La Haye, Feb 13 2005

Integral representation as n-th moment of a positive function on the positive axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/2)/sqrt(2*Pi*x) dx, n >= 0. - Karol A. Penson, Oct 10 2005

a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006

a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for iDavid Callan, Sep 25 2006

a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006

Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006

a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006

a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan, Mar 30 2007

From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start)

a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations.

This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)

From Ross Drewe, Mar 16 2008: (Start)

This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.

If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.

For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.

By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}

Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)

A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller, Apr 25 2008

a(n+1) = Sum_{j=0..n} A074060(n,j) * 2^j. - Tom Copeland, Sep 01 2008

From Emeric Deutsch, Jun 05 2009: (Start)

a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.

a(n) = Sum_{k>=0} k*A079267(n,k).

(End)

Hankel transform is A137592. - Paul Barry, Sep 18 2009

(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009

a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009

The Hankel transform of a(n+1) is A168467. - Paul Barry, Dec 04 2009

Partial products of odd numbers. - Juri-Stepan Gerasimov, Oct 17 2010

See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011

a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011

a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). - Leonid Bedratyuk, Jun 01 2012

For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013

a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013

a(n) is the size of the Brauer monoid on 2n points (see A227545). - James Mitchell, Jul 28 2013

For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014

a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014

For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014

Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014

a(n) = the number of relaxed compacted binary trees of right height at most one of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017

Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017

From Christopher J. Smyth, Jan 26 2018: (Start)

a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)

Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.

(End)

a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021

Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021

From Tom Copeland, Jun 14 2021: (Start)

Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).

Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial.

These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991.

a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End)

Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021

b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022

Number of ways n labeled objects can be distributed into k nonempty parcels. Also number of special terms in n variables with maximal degree k.

In older terminology these are called differences of 0. - Michael Somos, Oct 08 2003

Number of surjections (onto functions) from an n-element set to a k-element set.

Also coefficients (in ascending order) of so-called ordered Bell polynomials.

(k-1)!*Stirling2(n,k-1) is the number of chain topologies on an n-set having k open sets [Stephen].

Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007

Correction of comment before: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (an (n-1)-dimensional polytope). - Tilman Piesk, Oct 29 2014

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. - Tom Copeland, Sep 29 2008, Oct 07 2008

Further to the comments of Tom Copeland above, the permutohedron of type A_3 can be taken as the truncated octahedron. Its dual is the tetrakis hexahedron, a simplicial polyhedron, with f-vector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p. 21]. The corresponding h-vectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of f-vectors for type B and type D permutohedra respectively. - Peter Bala, Oct 26 2008

Subtriangle of triangle in A131689. - Philippe Deléham, Nov 03 2008

Since T(n,k) counts surjective functions and surjective functions are "consistent", T(n,k) satisfies a binomial identity, namely, T(n,x+y) = Sum_{j=0..n} C(n,j)*T(j,x)*T(n-j,y). For definition of consistent functions and a generalized binomial identity, see "Toy stories and combinatorial identities" in the link section below. - Dennis P. Walsh, Feb 24 2012

T(n,k) is the number of labeled forests on n+k vertices satisfying the following two conditions: (i) each forest consists of exactly k rooted trees with roots labeled 1, 2, ..., k; (ii) every root has at least one child vertex. - Dennis P. Walsh, Feb 24 2012

The triangle is the inverse binomial transform of triangle A028246, deleting the left column and shifting up one row. - Gary W. Adamson, Mar 05 2012

See A074909 for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014

E.g.f. for the shifted signed polynomials is G(x,t) = (e^t-1)/[1+(1+x)(e^t-1)] = 1-(1+x)(e^t-1) + (1+x)^2(e^t-1)^2 - ... (see also A008292 and A074909), which has the infinitesimal generator g(x,u)d/du = [(1-x*u)(1-(1+x)u)]d/du, i.e., exp[t*g(x,u)d/du]u eval. at u=0 gives G(x,t), and dG(x,t)/dt = g(x,G(x,t)). The compositional inverse is log((1-xt)/(1-(1+x)t)). G(x,t) is a generating series associated to the generalized Hirzebruch genera. See the G. Rzadowski link for the relation of the derivatives of g(x,u) to solutions of the Riccatt differential equation, soliton solns. to the KdV equation, and the Eulerian and Bernoulli numbers. In addition A145271 connects products of derivatives of g(x,u) and the refined Eulerian numbers to the inverse of G(x,t), which gives the normalized, reverse face polynomials of the simplices (A135278, divided by n+1). See A028246 for the generator g(x,u)d/dx. - Tom Copeland, Nov 21 2014

For connections to toric varieties and Eulerian polynomials, see the Dolgachev and Lunts and the Stembridge links. - Tom Copeland, Dec 31 2015

See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra. - Tom Copeland, Nov 14 2016

T(n, k) appears in a Worpitzky identity relating monomials to binomials: x^n = Sum_{k=1..n} T(n, k)*binomial(x,k), n >= 1. See eq. (11.) of the Worpitzky link on p. 209. The relation to the Eulerian numbers is given there in eqs. (14.) and (15.). See the formula below relating to A008292. See also Graham et al. eq. (6.10) (relating monomials to falling factorials) on p. 248 (2nd ed. p. 262). The Worpitzky identity given in the Graham et al. reference as eq. (6.37) (2nd ed. p. 269) is eq. (5.), p. 207, of Worpitzky. - Wolfdieter Lang, Mar 10 2017

T(n, m) is also the number of minimum clique coverings and minimum matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 26 2017

From the Hasan and Franco and Hasan papers: The m-permutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5-cell. The first three are well-known from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)-permutohedron. Relations to toric Calabi-Yau Kahler manifolds are also discussed. - Tom Copeland, May 14 2020

From Manfred Boergens, Jul 25 2021: (Start)

Number of n X k binary matrices with row sums = 1 and no zero columns. These matrices are a subset of the matrices defining A183109.

The distribution into parcels in the leading comment can be regarded as a covering of [n] by tuples (A_1,...,A_k) in P([n])^k with nonempty and disjoint A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the non-disjoint case see A183109 and A218695.

For tuples with "nonempty" dropped see A089072. For tuples with "nonempty and disjoint" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.

A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016

Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004

Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008

Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018

From Gus Wiseman, Dec 28 2019: (Start)

Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:

{1,2,3,4} {{1},{2},{3,4}} {{1},{2,3,4}}

{{1},{2,3},{4}} {{1,2},{3,4}}

{{1,2},{3},{4}} {{1,2,3},{4}}

{{1},{2,4},{3}} {{1,2,4},{3}}

{{1,3},{2},{4}} {{1,3},{2,4}}

{{1,4},{2},{3}} {{1,3,4},{2}}

{{1,4},{2,3}}

{{{1},{2,3}},{4}}

{{{1,2},{3}},{4}}

{{1},{{2},{3,4}}}

{{1},{{2,3},{4}}}

{{{1},{2,4}},{3}}

{{{1,2},{4}},{3}}

{{1},{{2,4},{3}}}

{{{1,3},{2}},{4}}

{{{1},{3,4}},{2}}

{{{1,3},{4}},{2}}

{{{1,4},{2}},{3}}

{{{1,4},{3}},{2}}

(End)

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

Second-order Eulerian numbers <> = T(n,k+1) count the permutations of the multiset {1,1,2,2,...,n,n} with k ascents with the restriction that for all m, all integers between the two copies of m are less than m. In particular, the two 1s are always next to each other.

When seen as coefficients of polynomials with descending exponents, evaluations are in A000311 (x=2) and A001662 (x=-1).

The row reversed triangle is A112007. There one can find comments on the o.g.f.s for the diagonals of the unsigned Stirling1 triangle |A008275|.

Stirling2(n,n-k) = Sum_{m=0..k-1} T(k,m+1)*binomial(n+k-1+m, 2*k), k>=1. See the Graham et al. reference p. 271 eq. (6.43).

This triangle is the coefficient triangle of the numerator polynomials appearing in the o.g.f. for the k-th diagonal (k >= 1) of the Stirling2 triangle A048993.

The o.g.f. for column k satisfies the recurrence G(k,x) = x*(2*x*(d/dx)G(k-1,x) + (2-k)*G(k-1,x))/(1-k*x), k >= 2, with G(1,x) = 1/(1-x). - Wolfdieter Lang, Oct 14 2005

This triangle is in some sense generated by the differential equation y' = 1 - 2/(1+x+y). (This is the differential equation satisfied by the function defined implicitly as x+y=exp(x-y).) If we take y = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + ... and assume a(0)=c then all the a's may be calculated formally in terms of c and we have a(1) = (c-1)/(c+1) and, for n > 1, a(n) = 2^n/n! (1+c)^(1-2n)( T(n,1)c - T(n,2)c^2 + T(n,3)c^3 - ... + (-1)^(n-1) T(n,n)c^n ). - Moshe Shmuel Newman, Aug 08 2007

From the recurrence relation, the generating function F(x,y) := 1 + Sum_{n>=1, 1<=k<=n} [T(n,k)x^n/n!*y^k] satisfies the partial differential equation F = (1/y-2x)F_x + (y-1)F_y, with (non-elementary) solution F(x,y) = (1-y)/(1-Phi(w)) where w = y*exp(x(y-1)^2-y) and Phi(x) is defined by Phi(x) = x*exp(Phi(x)). By Lagrange inversion (see Wilf's book "generatingfunctionology", page 168, Example 1), Phi(x) = Sum_{n>=1} n^(n-1)*x^n/n!. Thus Phi(x) can alternatively be described as the e.g.f. for rooted labeled trees on n vertices A000169. - David Callan, Jul 25 2008

A method for solving PDEs such as the one above for F(x,y) is described in the Klazar reference (see pages 207-208). In his case, the auxiliary ODE dy/dx = b(x,y)/a(x,y) is exact; in this case it is not exact but has an integrating factor depending on y alone, namely y-1. The e.g.f. for the row sums A001147 is 1/sqrt(1-2*x) and the demonstration that F(x,1) = 1/sqrt(1-2*x) is interesting: two applications of l'Hopital's rule to lim_{y->1}F(x,y) yield F(x,1) = 1/(1-2x)*1/F(x,1). So l'Hopital's rule doesn't directly yield F(x,1) but rather an equation to be solved for F(x,1)!. - David Callan, Jul 25 2008

From Tom Copeland, Oct 12 2008; May 19 2010: (Start)

Let P(0,t)= 0, P(1,t)= 1, P(2,t)= t, P(3,t)= t + 2 t^2, P(4,t)= t + 8 t^2 + 6 t^3, ... be the row polynomials of the present array, then

exp(x*P(.,t)) = ( u + Tree(t*exp(u)) ) / (1-t) = WD(x*(1-t), t/(1-t)) / (1-t)

where u = x*(1-t)^2 - t, Tree(x) is the e.g.f. of A000169 and WD(x,t) is the e.g.f. for A134991, relating the Ward and 2-Eulerian polynomials by a simple transformation.

Note also apparently P(4,t) / (1-t)^3 = Ward Poly(4, t/(1-t)) = essentially an e.g.f. for A093500.

The compositional inverse of f(x,t) = exp(P(.,t)*x) about x=0 is

g(x,t) = ( x - (t/(1-t)^2)*(exp(x*(1-t))-x*(1-t)-1) )

= x - t*x^2/2! - t*(1-t)*x^3/3! - t*(1-t)^2*x^4/4! - t*(1-t)^3*x^5/5! - ... .

Can apply A134685 to these coefficients to generate f(x,t). (End)

Triangle A163936 is similar to the one given above except for an extra right hand column [1, 0, 0, 0, ... ] and that its row order is reversed. - Johannes W. Meijer, Oct 16 2009

From Tom Copeland, Sep 04 2011: (Start)

Let h(x,t) = 1/(1-(t/(1-t))*(exp(x*(1-t))-1)), an e.g.f. in x for row polynomials in t of A008292, then the n-th row polynomial in t of the table A008517 is given by ((h(x,t)*D_x)^(n+1))x with the derivative evaluated at x=0.

Also, df(x,t)/dx = h(f(x,t),t) where f(x,t) is an e.g.f. in x of the row polynomials in t of A008517, i.e., exp(x*P(.,t)) in Copeland's 2008 comment. (End)

The rows are the h-vectors of A134991. - Tom Copeland, Oct 03 2011

Hilbert series of the pre-WDVV ring, thus h-vectors of the Whitehouse simplicial complex (cf. Readdy, Table 1). - Tom Copeland, Sep 20 2014

Arises in Buckholtz's analysis of the error term in the series for exp(nz). - N. J. A. Sloane, Jul 05 2016

This sequence counts the "almost triangular" partitions of n. A partition is triangular if it is of the form 0+1+2+...+k. Examples: 3=0+1+2, 6=0+1+2+3. An "almost triangular" partition is a triangular partition with at most 1 added to each of the parts. Examples: 7 = 1+1+2+3 = 0+2+2+3 = 0+1+3+3 = 0+1+2+4. Thus a(7)=4. 8 = 1+2+2+3 = 1+1+3+3 = 1+1+2+4 = 0+2+3+3 = 0+2+2+4 = 0+1+3+4 so a(8)=6. - Moshe Shmuel Newman, Dec 19 2002

The "almost triangular" partitions are the ones cycled by the operation of "Bulgarian solitaire", as defined by Martin Gardner.

Start with A007318 - I (I = Identity matrix), then delete right border of zeros. - Gary W. Adamson, Jun 15 2007

Also the number of increasing acyclic functions from {1..n-k+1} to {1..n+2}. A function f is acyclic if for every subset B of the domain the image of B under f does not equal B. For example, T(3,1)=4 since there are exactly 4 increasing acyclic functions from {1,2,3} to {1,2,3,4,5}: f1={(1,2),(2,3),(3,4)}, f2={(1,2),(2,3),(3,5)}, f3={(1,2),(2,4),(3,5)} and f4={(1,3),(2,4),(4,5)}. - Dennis P. Walsh, Mar 14 2008

Second Bernoulli polynomials are (from A164555 instead of A027641) B2(n,x) = 1; 1/2, 1; 1/6, 1, 1; 0, 1/2, 3/2, 1; -1/30, 0, 1, 2, 1; 0, -1/6, 0, 5/3, 5/2, 1; ... . Then (B2(n,x)/A002260) = 1; 1/2, 1/2; 1/6, 1/2, 1/3; 0, 1/4, 1/2, 1/4; -1/30, 0, 1/3, 1/2, 1/5; 0, -1/12, 0, 5/12, 1/2, 1/6; ... . See (from Faulhaber 1631) Jacob Bernoulli Summae Potestatum (sum of powers) in A159688. Inverse polynomials are 1; -1, 2; 1, -3, 3; -1, 4, -6, 4; ... = A074909 with negative even diagonals. Reflected A053382/A053383 = reflected B(n,x) = RB(n,x) = 1; -1/2, 1; 1/6, -1, 1; 0, 1/2, -3/2, 1; ... . A074909 is inverse of RB(n,x)/A002260 = 1; -1/2, 1/2; 1/6, -1/2, 1/3; 0, 1/4, -1/2, 1/4; ... . - Paul Curtz, Jun 21 2010

A054143 is the fission of the polynomial sequence (p(n,x)) given by p(n,x) = x^n + x^(n-1) + ... + x + 1 by the polynomial sequence ((x+1)^n). See A193842 for the definition of fission. - Clark Kimberling, Aug 07 2011

Reversal of A135278. - Philippe Deléham, Feb 11 2012

For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 19 2013

For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013

From A238363, the operator equation d/d(:xD:)f(xD)={exp[d/d(xD)]-1}f(xD) = f(xD+1)-f(xD) follows. Choosing f(x) = x^n and using :xD:^n/n! = binomial(xD,n) and (xD)^n = Bell(n,:xD:), the Bell polynomials of A008277, it follows that the lower triangular matrix [padded A074909]

A) = [St2]*[dP]*[St1] = A048993*A132440*[padded A008275]

B) = [St2]*[dP]*[St2]^(-1)

C) = [St1]^(-1)*[dP]*[St1],

where [St1]=padded A008275 just as [St2]=A048993=padded A008277 whereas [padded A074909]=A007318-I with I=identity matrix. - Tom Copeland, Apr 25 2014

T(n,k) generated by m-gon expansions in the case of odd m with "vertex to side" version or even m with "vertex to vertes" version. Refer to triangle expansions in A061777 and A101946 (and their companions for m-gons) which are "vertex to vertex" and "vertex to side" versions respectively. The label values at each iteration can be arranged as a triangle. Any m-gon can also be arranged as the same triangle with conditions: (i) m is odd and expansion is "vertex to side" version or (ii) m is even and expansion is "vertex to vertex" version. m*Sum_{i=1..k} T(n,k) gives the total label value at the n-th iteration. See also A247976. Vertex to vertex: A061777, A247618, A247619, A247620. Vertex to side: A101946, A247903, A247904, A247905. - Kival Ngaokrajang Sep 28 2014

From Tom Copeland, Nov 12 2014: (Start)

With P(n,x) = [(x+1)^(n+1)-x^(n+1)], the row polynomials of this entry, Up(n,x) = P(n,x)/(n+1) form an Appell sequence of polynomials that are the umbral compositional inverses of the Bernoulli polynomials B(n,x), i.e., B[n,Up(.,x)] = x^n = Up[n,B(.,x)] under umbral substitution, e.g., B(.,x)^n = B(n,x).

The e.g.f. for the Bernoulli polynomials is [t/(e^t - 1)] e^(x*t), and for Up(n,x) it's exp[Up(.,x)t] = [(e^t - 1)/t] e^(x*t).

Another g.f. is G(t,x) = log[(1-x*t)/(1-(1+x)*t)] = log[1 + t /(1 + -(1+x)t)] = t/(1-t*Up(.,x)) = Up(0,x)*t + Up(1,x)*t^2 + Up(2,x)*t^3 + ... = t + (1+2x)/2 t^2 + (1+3x+3x^2)/3 t^3 + (1+4x+6x^2+4x^3)/4 t^4 + ... = -log(1-t*P(.,x)), expressed umbrally.

The inverse, Ginv(t,x), in t of the g.f. may be found in A008292 from Copeland's list of formulas (Sep 2014) with a=(1+x) and b=x. This relates these two sets of polynomials to algebraic geometry, e.g., elliptic curves, trigonometric expansions, Chebyshev polynomials, and the combinatorics of permutahedra and their duals.

Ginv(t,x) = [e^((1+x)t) - e^(xt)] / [(1+x) * e^((1+x)t) - x * e^(xt)] = [e^(t/2) - e^(-t/2)] / [(1+x)e^(t/2) - x*e^(-t/2)] = (e^t - 1) / [1 + (1+x) (e^t - 1)] = t - (1 + 2 x) t^2/2! + (1 + 6 x + 6 x^2) t^3/3! - (1 + 14 x + 36 x^2 + 24 x^3) t^4/4! + ... = -exp[-Perm(.,x)t], where Perm(n,x) are the reverse face polynomials, or reverse f-vectors, for the permutahedra, i.e., the face polynomials for the duals of the permutahedra. Cf. A090582, A019538, A049019, A133314, A135278.

With L(t,x) = t/(1+t*x) with inverse L(t,-x) in t, and Cinv(t) = e^t - 1 with inverse C(t) = log(1 + t). Then Ginv(t,x) = L[Cinv(t),(1+x)] and G(t,x) = C[L[t,-(1+x)]]. Note L is the special linear fractional (Mobius) transformation.

Connections among the combinatorics of the permutahedra, simplices (cf. A135278), and the associahedra can be made through the Lagrange inversion formula (LIF) of A133437 applied to G(t,x) (cf. A111785 and the Schroeder paths A126216 also), and similarly for the LIF A134685 applied to Ginv(t,x) involving the simplicial Whitehouse complex, phylogenetic trees, and other structures. (See also the LIFs A145271 and A133932). (End)

R = x - exp[-[B(n+1)/(n+1)]D] = x - exp[zeta(-n)D] is the raising operator for this normalized sequence UP(n,x) = P(n,x) / (n+1), that is, R UP(n,x) = UP(n+1,x), where D = d/dx, zeta(-n) is the value of the Riemann zeta function evaluated at -n, and B(n) is the n-th Bernoulli number, or constant B(n,0) of the Bernoulli polynomials. The raising operator for the Bernoulli polynomials is then x + exp[-[B(n+1)/(n+1)]D]. [Note added Nov 25 2014: exp[zeta(-n)D] is abbreviation of exp(a.D) with (a.)^n = a_n = zeta(-n)]. - Tom Copeland, Nov 17 2014

The diagonals T(n, n-m), for n >= m, give the m-th iterated partial sum of the positive integers; that is A000027(n+1), A000217(n), A000292(n-1), A000332(n+1), A000389(n+1), A000579(n+1), A000580(n+1), A000581(n+1), A000582(n+1), ... . - Wolfdieter Lang, May 21 2015

The transpose gives the numerical coefficients of the Maurer-Cartan form matrix for the general linear group GL(n,1) (cf. Olver, but note that the formula at the bottom of p. 6 has an error--the 12 should be a 15). - Tom Copeland, Nov 05 2015

The left invariant Maurer-Cartan form polynomial on p. 7 of the Olver paper for the group GL^n(1) is essentially a binomial convolution of the row polynomials of this entry with those of A133314, or equivalently the row polynomials generated by the product of the e.g.f. of this entry with that of A133314, with some reindexing. - Tom Copeland, Jul 03 2018

From Tom Copeland, Jul 10 2018: (Start)

The first column of the inverse matrix is the sequence of Bernoulli numbers, which follows from the umbral definition of the Bernoulli polynomials (B.(0) + x)^n = B_n(x) evaluated at x = 1 and the relation B_n(0) = B_n(1) for n > 1 and -B_1(0) = 1/2 = B_1(1), so the Bernoulli numbers can be calculated using Cramer's rule acting on this entry's matrix and, therefore, from the ratios of volumes of parallelepipeds determined by the columns of this entry's square submatrices. - Tom Copeland, Jul 10 2018

Umbrally composing the row polynomials with B_n(x), the Bernoulli polynomials, gives (B.(x)+1)^(n+1) - (B.(x))^(n+1) = d[x^(n+1)]/dx = (n+1)*x^n, so multiplying this entry as a lower triangular matrix (LTM) by the LTM of the coefficients of the Bernoulli polynomials gives the diagonal matrix of the natural numbers. Then the inverse matrix of this entry has the elements B_(n,k)/(k+1), where B_(n,k) is the coefficient of x^k for B_n(x), and the e.g.f. (1/x) (e^(xt)-1)/(e^t-1). (End)

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