cp's OEIS Frontend

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

Smallest number of straight line crossing-free spanning trees on n points in the plane.

Number of dissections of some convex polygon by nonintersecting diagonals into polygons with an odd number of sides and having a total number of 2n+1 edges (sides and diagonals). - Emeric Deutsch, Mar 06 2002

Number of lattice paths of n East steps and 2n North steps from (0,0) to (n,2n) and lying weakly below the line y=2x. - David Callan, Mar 14 2004

With interpolated zeros, this has g.f. 2*sqrt(3)*sin(arcsin(3*sqrt(3)*x/2)/3)/(3*x) and a(n) = C(n+floor(n/2),floor(n/2))*C(floor(n/2),n-floor(n/2))/(n+1). This is the first column of the inverse of the Riordan array (1-x^2,x(1-x^2)) (essentially reversion of y-y^3). - Paul Barry, Feb 02 2005

Number of 12312-avoiding matchings on [2n].

Number of complete ternary trees with n internal nodes, or 3n edges.

Number of rooted plane trees with 2n edges, where every vertex has even outdegree ("even trees").

a(n) is the number of noncrossing partitions of [2n] with all blocks of even size. E.g.: a(2)=3 counts 12-34, 14-23, 1234. - David Callan, Mar 30 2007

Pfaff-Fuss-Catalan sequence C^{m}_n for m=3, see the Graham et al. reference, p. 347. eq. 7.66.

Also 3-Raney sequence, see the Graham et al. reference, p. 346-7.

The number of lattice paths from (0,0) to (2n,0) using an Up-step=(1,1) and a Down-step=(0,-2) and staying above the x-axis. E.g., a(2) = 3; UUUUDD, UUUDUD, UUDUUD. - Charles Moore (chamoore(AT)howard.edu), Jan 09 2008

a(n) is (conjecturally) the number of permutations of [n+1] that avoid the patterns 4-2-3-1 and 4-2-5-1-3 and end with an ascent. For example, a(4)=55 counts all 60 permutations of [5] that end with an ascent except 42315, 52314, 52413, 53412, all of which contain a 4-2-3-1 pattern and 42513. - David Callan, Jul 22 2008

Central terms of pendular triangle A167763. - Philippe Deléham, Nov 12 2009

With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} a(j) (-t)^j x^(2j+1). Let U(x,t)=(x-A(x,t))/t. Then DU(x,t)/Dt=dU/dt+U*dU/dx=0 and U(x,0)=x^3, i.e., U is a solution of the inviscid Burgers's, or Hopf, equation. Also U(x,t)=U(x-t*U(x,t),0) and dB(x,t)/dt = U(B(x,t),t) = x^3 = U(x,0). The characteristics for the Hopf equation are x(t) = x(0) + t*U(x(t),t) = x(0) + t*U(x(0),0) = x(0) + t*x(0)^3 = B(x(0),t). These results apply to all the Fuss-Catalan sequences with 3 replaced by n>0 and 2 by n-1 (e.g., A000108 with n=2 and A002293 with n=4), see also A086810, which can be generalized to A133437, for associahedra. - Tom Copeland, Feb 15 2014

Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Kreweras lattice (noncrossing partitions ordered by refinement) of size n, see the Bernardi & Bonichon (2009) and Kreweras (1972) references. - Noam Zeilberger, Jun 01 2016

Number of sum-indecomposable (4231,42513)-avoiding permutations. Conjecturally, number of sum-indecomposable (2431,45231)-avoiding permutations. - Alexander Burstein, Oct 19 2017

a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link. - Caleb Ji, May 14 2018

Number of complete quadrillages of 2n+2-gons. See Baryshnikov p. 12. See also Nov 10 2014 comments in A134264. - Tom Copeland, Jun 04 2018

a(n) is the number of 2-regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2-regular tortoise-sortable words on the alphabet [n] (see the Defant and Kravitz link). - Colin Defant, Sep 26 2018

a(n) is the number of Motzkin paths of length 3n with n steps of each type, with the condition that (1, 0) and (1, 1) steps alternate (starting with (1, 0)). - Helmut Prodinger, Apr 08 2019

a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 312 and 1342. - Colin Defant, Jun 08 2019

The compositional inverse o.g.f. pair in Copeland's comment above are related to a pair of quantum fields in Balduf's thesis by Theorem 4.2 on p. 92. - Tom Copeland, Dec 13 2019

The sequences of Fuss-Catalan numbers, of which this is the first after the Catalan numbers A000108 (the next is A002293), appear in articles on random matrices and quantum physics. See Banica et al., Collins et al., and Mlotkowski et al. Interpretations of these sequences in terms of the cardinality of specific sets of noncrossing partitions are provided by A134264. - Tom Copeland, Dec 21 2019

Call C(p, [alpha], g) the number of partitions of a cyclically ordered set with p elements, of cyclic type [alpha], and of genus g (the genus g Faa di Bruno coefficients of type [alpha]). This sequence counts the genus 0 partitions (non-crossing, or planar, partitions) of p = 3n into n parts of length 3: a(n) = C(3n, [3^n], 0). For genus 1 see A371250, for genus 2 see A371251. - Robert Coquereaux, Mar 16 2024

a(n) is the total number of down steps before the first up step in all 2_1-Dyck paths of length 3*n for n > 0. A 2_1-Dyck path is a lattice path with steps (1,2), (1,-1) that starts and ends at y = 0 and does not go below the line y = -1. - Sarah Selkirk, May 10 2020

a(n) is the number of pairs (A<=B) of noncrossing partitions of [n]. - Francesca Aicardi, May 28 2022

a(n) is the number of parking functions of size n avoiding the patterns 231 and 321. - Lara Pudwell, Apr 10 2023

Number of rooted polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {4,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024

This is instance k = 3 of the family {C(k, n)}A130564.%20-%20_Wolfdieter%20Lang">{n>=0} given in a comment in A130564. - _Wolfdieter Lang, Feb 05 2024

The number of Apollonian networks (planar 3-trees) with n+3 vertices with a given base triangle. - Allan Bickle, Feb 20 2024

Number of rooted polyominoes composed of n tetrahedral cells of the hyperbolic regular tiling with Schläfli symbol {3,3,oo}. A rooted polyomino has one external face identified, and chiral pairs are counted as two. a(n) = T(n) in the second Beineke and Pippert link. - Robert A. Russell, Mar 20 2024

If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318.

Yang & Jiang (2021) call these the small 2-Schroeder numbers. - N. J. A. Sloane, Mar 28 2021

There are two schools of thought about the index for the first term. I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.

a(n) is the number of ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are ignored.

Also length of list produced by a variant of the Catalan producing iteration: replace each integer k with the list 0,1,..,k,k+1,k,...,1,0 and get the length a(n) of the resulting (flattened) list after n iterations. - Wouter Meeussen, Nov 11 2001

Stanley gives several other interpretations for these numbers.

Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no peaks at level 1. Example: a(2)=3 because among the six Schroeder paths of semilength two HH, UHD, UUDD, HUD, UDH and UDUD, only the first three have no peaks at level 1. - Emeric Deutsch, Dec 27 2003

a(n+1) is the number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004

Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.

Also row sums of A086810, A033282, A126216. - Philippe Deléham, May 09 2004

a(n+1) is the number of pairs (u,v) of same-length compositions of n, 0's allowed in u but not in v and u dominates v (meaning u_1 >= v_1, u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts (2,2), (1+1,1+1), (2+0,1+1). - David Callan, Jul 20 2005

The big Schroeder number (A006318) is the number of Schroeder paths from (0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)). These paths fall in two classes: those with steps on the main diagonal and those without. These two classes are equinumerous and the number of paths in either class is the little Schroeder number a(n) (half the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005

With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each upstep U getting one of 2 colors and each flatstep F getting one of 3 colors. Example. With their colors immediately following upsteps/flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D, F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan, Aug 16 2006

Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009

Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014

Number of ordered trees with no vertex of outdegree 1 and having n+1 leaves (called sometimes Schröder trees). - Emeric Deutsch, Dec 13 2014

Number of dissections of a convex (n+2)-gon by nonintersecting diagonals. Example: a(2)=3 because for a square ABCD we have (i) no diagonal, (ii) dissection with diagonal AC, and (iii) dissection with diagonal BD. - Emeric Deutsch, Dec 13 2014

The little Schroeder numbers are the moments of the Marchenko-Pastur law for the case c=2 (although the moment m0 is 1/2 instead of 1): 1/2, 1, 3, 11, 45, 197, 903, ... - Jose-Javier Martinez, Apr 07 2015

Number of generalized Motzkin paths with no level steps at height 0, from (0,0) to (2n,0), and consisting of steps U=(1,1), D=(1,-1) and H2=(2,0). For example, for n=3, we have the 11 paths: UDUDUD, UUDDUD, UDUUDD, UH2DUD, UDUH2D, UH2H2D, UUDUDD, UUUDDD, UUH2DD, UUDH2D, UH2UDD. - José Luis Ramírez Ramírez, Apr 20 2015

REVERT transform of A225883. - Vladimir Reshetnikov, Oct 25 2015

Total number of (nonempty) faces of all dimensions in the associahedron K_{n+1} of dimension n-1. For example, K_4 (a pentagon) includes 5 vertices and 5 edges together with K_4 itself (5 + 5 + 1 = 11), while K_5 includes 14 vertices, 21 edges and 9 faces together with K_5 itself (14 + 21 + 9 + 1 = 45). - Noam Zeilberger, Sep 17 2018

a(n) is the number of interval posets of permutations with n minimal elements that have exactly two realizers, up to a shift by 1 in a(4). See M. Bouvel, L. Cioni, B. Izart, Theorem 17 page 13. - Mathilde Bouvel, Oct 21 2021

a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_1 = 1, (ii) u_i <= i for all i, (iii) the nonzero u_i are weakly increasing. For example, a(2) = 3 counts 10, 11, 12, and a(3) = 11 counts 100, 101, 102, 103, 110, 111, 112, 113, 120, 122, 123. See link below. - David Callan, Dec 19 2021

a(n) is the number of parking functions of size n avoiding the patterns 132 and 213. - Lara Pudwell, Apr 10 2023

a(n+1) is the number of Schroeder paths from (0,0) to (2n,0) in which level steps at height 0 come in 2 colors. - Alexander Burstein, Jul 23 2023

Also called Motzkin summands or ring numbers.

The old name was "Motzkin sums", used in certain publications. The sequence has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g., A001006(4) = 9 = 3 + 6 = a(4) + a(5).

Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers). - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04 2000

Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - Emeric Deutsch, Mar 06 2002

Number of Motzkin paths of length n with no horizontal steps at level 0. - Emeric Deutsch, Nov 09 2003

Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - Emeric Deutsch, Dec 05 2003

Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09 2004

Difference between central trinomial coefficient and its predecessor. Example: a(6) = 15 = 141 - 126 and (1 + x + x^2)^6 = ... + 126*x^5 + 141*x^6 + ... (Catalan number A000108(n) is the difference between central binomial coefficient and its predecessor.) - David Callan, Feb 07 2004

a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e., is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - David Callan, Jul 20 2005

The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, ...]; example: Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1. - Philippe Deléham, May 28 2005

The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006

Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - Andrew V. Sutherland, Dec 02 2007

Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008

Starting with offset 3 = iterates of M * [1,1,1,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 08 2009

a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010

a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1 <= k <= floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010

a(n) is the number of derangements of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p) = (1/2)(3+1-1-3)=0. - Emeric Deutsch, May 29 2010

Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - David Scambler, Apr 17 2012

This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU with U, DD with D, UD with a blue flatstep (F), DU with a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. - David Callan, Apr 25 2012

From Nolan Wallach, Aug 20 2014: (Start)

Let ch[part1, part2] be the value of the character of the symmetric group on n letters corresponding to the partition part1 of n on the conjucgacy class given by part2. Let A[n] be the set of (n+1) partitions of 2n with parts 1 or 2. Then deleting the first term of the sequence one has a(n) = Sum_{k=1..n+1} binomial(n,k-1)*ch[[n,n], A[n][[k]]])/2^n. This via the Frobenius Character Formula can be interpreted as the dimension of the SL(n,C) invariants in tensor^n (wedge^2 C^n).

Explanation: Let p_j denote sum (x_i)^j the sum in k variables. Then the Frobenius formula says then (p_1)^j_1 (p_2)^j_2 ... (p_r)^j_r is equal to sum(lambda, ch[lambda, 1^j_12^j_2 ... r^j_r] S_lambda) with S_lambda the Schur function corresponding to lambda. This formula implies that the coefficient of S([n,n]) in (((p_1)^1+p_2)/2)^n in its expansion in terms of Schur functions is the right hand side of our formula. If we specialize the number of variables to 2 then S[n,n](x,y)=(xy)^n. Which when restricted to y=x^(-1) is 1. That is it is 1 on SL(2).

On the other hand ((p_1)^2+p_2)/2 is the complete homogeneous symmetric function of degree 2 that is tr(S^2(X)). Thus our formula for a(n) is the same as that of Samson Black above since his V is the same as S^2(C^2) as a representation of SL(2). On the other hand, if we multiply ch(lambda) by sgn you get ch(Transpose(lambda)). So ch([n,n]) becomes ch([2,...,2]) (here there are n 2's). The formula for a(n) is now (1/2^n)*Sum_{j=0..n} ch([2,..,2], 1^(2n-2j) 2^j])*(-1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2-p_2)/2)^n. But ((p_1)^2-p_2)/2 in n variables is the second elementary symmetric function which is the character of wedge^2 C^n and S_(2,...,2) is 1 on SL(n).

(End)

a(n) = number of noncrossing partitions (A000108) of [n] that contain no singletons, also number of nonnesting partitions (A000108) of [n] that contain no singletons. - David Callan, Aug 27 2014

From Tom Copeland, Nov 02 2014: (Start)

Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).

Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].

Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).

BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].

Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).

Various relations among the o.g.f.s may be easily constructed, such as Fib[-Mot(-x)] = -P[P(-x)] = x/(1-2*x) a generating fct for 2^n.

Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1]. (End)

Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the non-crossing partitions he describes. - Tom Copeland, Nov 09 2014

The number of lattice paths from (0,0) to (n,0) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-k) where k is a positive integer. For example, a(4) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - Nicholas Ham, Aug 19 2015

A series created using 2*(a(n) + a(n+1)) + (a(n+1) + a(n+2)) has Hankel transform of F(2n), offset 3, F being a Fibonacci number, A001906 (Empirical observation). - Tony Foster III, Jul 30 2016

The series a(n) + A001006(n) has Hankel transform F(2n+1), offset n=1, F being the Fibonacci bisection A001519 (empirical observation). - Tony Foster III, Sep 05 2016

The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n. Moreover, the number of such algebras having the double centraliser property with respect to a minimal faithful projective-injective module equals the number of Riordan paths, that is, Motzkin paths without level-steps at height zero, of length n." - Eric M. Schmidt, Dec 16 2017

A connection to the Thue-Morse sequence: (-1)^a(n) = (-1)^A010060(n) * (-1)^A010060(n+1) = A106400(n) * A106400(n+1). - Vladimir Reshetnikov, Jul 21 2019

Named by Bernhart (1999) after the American mathematician John Riordan (1903-1988). - Amiram Eldar, Apr 15 2021

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

Row sums: A006318 (Schroeder numbers). Essentially same as triangle A060693 transposed.

T(n,k) is number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k U's. E.g., T(2,1)=3 because we have UHD, UDH and HUD. - Emeric Deutsch, Dec 06 2003

Little Schroeder numbers A001003 have a(n) = Sum_{k=0..n} A088617(n,k)*(-1)^(n-k)*2^k. - Paul Barry, May 24 2005

Conjecture: The expected number of U's in a Schroeder n-path is asymptotically Sqrt[1/2]*n for large n. - David Callan, Jul 25 2008

T(n, k) is also the number of order-preserving and order-decreasing partial transformations (of an n-chain) of width k (width(alpha) = |Dom(alpha)|). - Abdullahi Umar, Oct 02 2008

The antidiagonals of this lower triangular matrix are the rows of A055151. - Tom Copeland, Jun 17 2015

T(n+3, k) is also the number of compatible k-sets of cluster variables in Fomin and Zelevinsky's cluster algebra of finite type A_n. Take a row of this triangle regarded as a polynomial in x and rewrite as a polynomial in y := x+1. The coefficients of the polynomial in y give a row of the triangle of Narayana numbers A001263. For example, x^2 + 5*x + 5 = y^2 + 3*y + 1. - Paul Boddington, Mar 07 2003

Number of standard Young tableaux of shape (k+1,k+1,1^(n-k-3)), where 1^(n-k-3) denotes a sequence of n-k-3 1's (see the Stanley reference).

Number of k-dimensional 'faces' of the n-dimensional associahedron (see Simion, p. 168). - Mitch Harris, Jan 16 2007

Mirror image of triangle A126216. - Philippe Deléham, Oct 19 2007

For relation to Lagrange inversion or series reversion and the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. - Tom Copeland, Sep 29 2008

Row generating polynomials 1/(n+1)*Jacobi_P(n,1,1,2*x+1). Row n of this triangle is the f-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p. 60]. See A001263 for the corresponding array of h-vectors for associahedra of type A_n. See A063007 and A080721 for the f-vectors for associahedra of type B and type D respectively. - Peter Bala, Oct 28 2008

f-vectors of secondary polytopes for Grobner bases for optimization and integer programming (see De Loera et al. and Thomas). - Tom Copeland, Oct 11 2011

From Devadoss and O'Rourke's book: The Fulton-MacPherson compactification of the configuration space of n free particles on a line segment with a fixed particle at each end is the n-Dim Stasheff associahedron whose refined f-vector is given in A133437 which reduces to A033282. - Tom Copeland, Nov 29 2011

Diagonals of A132081 are rows of A033282. - Tom Copeland, May 08 2012

The general results on the convolution of the refined partition polynomials of A133437, with u_1 = 1 and u_n = -t otherwise, can be applied here to obtain results of convolutions of these polynomials. - Tom Copeland, Sep 20 2016

The signed triangle t(n, k) =(-1)^k* T(n+2, k-1), n >= 1, k = 1..n, seems to be obtainable from the partition array A111785 (in Abramowitz-Stegun order) by adding the entries corresponding to the partitions of n with the number of parts k. E.g., triangle t, row n=4: -1, (6+3) = 9, -21, 14. - Wolfdieter Lang, Mar 17 2017

The preceding conjecture by Lang is true. It is implicit in Copeland's 2011 comments in A086810 on the relations among a gf and its compositional inverse for that entry and inversion through A133437 (a differently normalized version of A111785), whose integer partitions are the same as those for A134685. (An inversion pair in Copeland's 2008 formulas below can also be used to prove the conjecture.) In addition, it follows from the relation between the inversion formula of A111785/A133437 and the enumeration of distinct faces of associahedra. See the MathOverflow link concernimg Loday and the Aguiar and Ardila reference in A133437 for proofs of the relations between the partition polynomials for inversion and enumeration of the distinct faces of the A_n associahedra, or Stasheff polytopes. - Tom Copeland, Dec 21 2017

The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/(n!*(n+1)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Oct 07 2022

Chapoton's observation above is correct: the precise expansion is (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/ (n!*(n+1)!) = Sum_{k = 0..n-1} (-1)^k*T(n+2,n-k-1)*binomial(x+2*n-k,2*n-k), as can be verified using the WZ algorithm. For example, n = 4 gives (x+1)*(x+2)^2*(x+3)^2*(x+4)^2*(x+5)/(4!*5!) = 14*binomial(x+8,8) - 21*binomial(x+7,7) + 9*binomial(x+6,6) - binomial(x+5,5). - Peter Bala, Jun 24 2023

The rows sum to A006318 (Schroeder numbers), the left column is A000108 (Catalan numbers); the next-to-left column is A001700, the alternating sum in each row but the first is 0.

T(n,k) is the number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k peaks. Example: T(2,1)=3 because we have UU*DD, U*DH and HU*D, the peaks being shown by *. E.g., T(n,k) = binomial(n,k)*binomial(2n-k,n-1)/n for n>0. - Emeric Deutsch, Dec 06 2003

A090181*A007318 as infinite lower triangular matrices. - Philippe Deléham, Oct 14 2008

T(n,k) is also the number of rooted plane trees with maximal degree 3 and k vertices of degree 2 (a node may have at most 2 children, and there are exactly k nodes with 1 child). Equivalently, T(n,k) is the number of syntactically different expressions that can be formed that use a unary operation k times, a binary operation n-k times, and nothing else (sequence of operands is fixed). - Lars Hellstrom (Lars.Hellstrom(AT)residenset.net), Dec 08 2009

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) = u(t) - u(0) = Ev[exp(u.* t) - u(0)] = log{Ev[(exp(z.* t))/z_0]} = Ev[-log(1- a.* t)], where the operator Ev denotes umbral evaluation of the umbral variables u., z. or a., e.g., Ev[a.^n + a.^m] = a_n + a_m . The relation between z_n and u_n is given in reference in A127671 and u_n = (n-1)! * a_n .

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

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

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

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

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

P(5,t) = (1')^(-9) * [ 105 (2')^4 - 105 (1') (2')^2 (3') + 10 (1')^2 (3')^2 + 15 (1')^2 (2') (4') - (1')^3 (5') ] * t^5 / 5!

P(6,t) = (1')^(-11) * [ -945 (2')^5 + 1260 (1') (2')^3 (3') - 280 (1')^2 (2') (3')^2 - 210 (1')^2 (2')^2 (4') + 35 (1')^3 (3')(4') + 21 (1')^3 (2')(5') - (1')^4 (6') ] * t^6 / 6!

P(7,t) = (1')^(-13) * [ 10395 (2')^6 - 17325 (1') (2')^4 (3') + (1')^2 [ 6300 (2')^2 (3')^2 + 3150 (2')^3 (4')] - (1')^3 [280 (3')^3 + 1260 (2')(3')(4') + 378 (2')^2(5')] + (1')^4 [35 (4')^2 + 56 (3')(5') + 28 (2')(6')] - (1')^5 (7') ] * t^7 / 7!

P(8,t) = (1')^(-15) * [ -135135 (2')^7 + 270270 (1') (2')^5 (3') - (1')^2 [ 138600 (2')^3 (3')^2 + 51975 (2')^4 (4')] + (1')^3 [15400 (2')(3')^3 + 34650 (2')^2(3')(4') + 6930 (2')^3(5')] - (1')^4 [2100 (3')^2(4') + 1575 (2')(4')^2 + 2520 (2')(3')(5') + 630 (2')^2(6') ] + (1')^5 [126 (4')(5') + 84 (3')(6') + 36 (2')(7')] - (1')^6 (8') ] * t^8 / 8!

...

Substituting ((m-1)') for (m') in each partition and ignoring the (0') factors, the partitions in the brackets of P(n,t) become those of n-1 listed in Abramowitz and Stegun on page 831 (in the reversed order) and the number of partitions in P(n,t) is given by A000041(n-1).

Combinatorial interpretations are given in the link.

From Tom Copeland, Jul 10 2018: (Start)

Coefficients occurring in prolongation for the special Euclidean group SE(2) and special affine group SA(2) in the Olver presentation on moving frames (MFP) in slides 33 and 42. These are a result of applying an iterated derivative of the form h(x)d/dx = d/dy as in this entry (more generally as g(x) d/dx as discussed in A145271). See also p. 6 of Olver's paper on contact forms, but note that the 12 should be a 15 in the formula for the compositional inverse of S(t).

Change variables in the MFP to obtain connections to the partition polynomials Prt_n = n! * P(n,1) above. Let delta and beta in the formulas for the equi-affine curves in MFP be L and B, respectively, and D_y = (1/(L-B*u_x)) d/dx = (1/w_x) d/dx. Then v_(yy) = (1/B) [-w_(xx)/(w_x)^3] in MFP (there is an overall sign error in MFP for v_(yy) and higher derivatives w.r.t. y), and (d/dy)^n v = v_n = (1/B)* [(1/w_1)*(d/dx)]^(n-2) [-w_2/(w_1)^3] for n > 1, with w_n = (d/dx)^n w. Consequently, in the partition polynomials Prt_n for n > 1 here substitute (n') = -B*u_n = w_n for n > 1 and (1') = L-B*u_1 = w_1, where u_n = (d/dx)^n u, and then divide by B. For example, v_4 = (1/B)*Prt_4 = (1/B)*4!*P(4,1) = (1/B) (L-B*u_n)^(-7) [-15*(-B*u_2)^3 + 10 (L-B*u_1)(-B*u_2)(-B*u_3) - (L-B*u_1)^2 (-B*u_4)], agreeing with v_4 in MFP except for the overall sign.

For the SE(2) transformation formulas in MFP, let w_x = cos(phi) + sin(phi)*u_x, and then the same transformations apply as above with cos(phi) and sin(phi) substituted for L and -B, respectively. (End)