cp's OEIS Frontend

Coefficients of reduced partition polynomials of A134264 for computing the complete partition polynomials for the Lagrange compositional inversion of A134264 (see Oct 2014 comment by Copeland there). Umbrally,

e^(x*t) * exp[Prt(.;1,0,h_2,..) * t] = exp[Prt(.;1,x,h_2,..) * t], where Prt(n;1,0,h_2,..,h_n) are the reduced (h_0 = 1 and h_1 = 0) partition polynomials of the complete polynomials Prt(n;h_0,h_1,h_2,..,h_n) of A134264.

Partitions are given in the order of those on page 831 of Abramowitz and Stegun. Formulas for the coefficients of the partitions are given in A134264.

Row sums are the Motzkin sums or Riordan numbers A005043. - Tom Copeland, Nov 09 2014

From Tom Copeland, Jul 03 2018: (Start)

The matrix and operator formalism for Sheffer Appell sequences leads to the following relations with D = d/dh_1.

Exp[Prt(.;1,0,h_2,..) * D] (h_1)^n = [h_1 + Prt(.;1,0,h_2,...)]^n = Prt(n;1,h_1,h_2,...), the partition polynomials of A134264 for g(t)/t with h_0 = 1.

For the umbral compositional inverses described below,

Exp[UPrt(.;1,0,h_2,..) * D] (h_1)^n = [h_1 + UPrt(.;1,0,h_2,...)]^n = UPrt(n;1,h_1,h_2,...).

The respective e.g.f.s are multiplicative inverses; that is, exp[Prt(.;1,0,h_2,..) * t] = 1/exp[UPrt(.;1,0,h_2,..) * t], so the formalism of A133314 applies.

The raising operator R such that R Prt(n;1,h_1,h_2,...) = Prt(n+1;1,h_1,h_2,...) is R = exp[Prt(.;1,0,h_2,...)*D] h_1 exp[UPrt(.;1,0,h_2,..)*D] since R Prt(n+1;1,h_1,h_2,...) = exp[Prt(.;1,0,h_2,...)*D] h_1 (h_1)^n = Prt(n+1;h_1,h_2,...) from the definition of the umbral compositional inverse. This may also be expressed as R = h_1 + d/dD log[exp[Prt(.;1,0,h_2,...) * D]], so, using A127671, R = h_1 + h_2 D + h_3 D^2/2! + (h_4 - h_2^2) D^3/3! + (h_5 - 5 h_2 h_3) D^4/4! + (h_6 - 9 h_2 h_4 + 5 h_2^3 - 7 h_3^2) D^5/5! + (h_7 - 28 h_3 h_4 - 14 h_2 h_5 + 56 h_2^2 h_3) D^6/6! + ... . (End)

This combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin et al. in "Planar Diagrams" via Eqn. 31 on p. 42.

Appears to be a refinement of A120986 and A108767 in that summing the coefficients of partitions with the same sum of exponents gives the rows or reverse rows of the two entries; for example, row 4 here becomes x + 8 xx + 4 x^2 + 28 x^2x + 14 x^4 = x + 12 x^2 + 28 x^3 + 14 x^4, which is row 4 of A108767. In short, replace each g_k or (k) by x in the formula section here to obtain the coarser entry or its reverse from this refined entry, apparently.

This also gives the relationship between moments and free cumulants in free probability theory restricted to an even number of noncrossing partitions as given by restricting the similar enumeration formuia on p. 34 of Novak and LaCroix to b_{2n} = G_{2n} and K_{2q} = g_{2q}. This is consistent with setting h_k to zero for odd k in A134264, e.g., doing so for the coefficients of t^7 for g(t) there gives G_6 here.

A125181 is another version of A134264, providing interpretations in terms of Dyck paths and trees.

A set of partition polynomials with these coefficients and the polynomials of A338135 can be generated by substitution of the refined Narayana, or noncrossing partition, polynomials N_n[h_1,...,h_n] of A134264 (h_0=1) into themselves--once for A338135 and twice for this entry--or by setting the indeterminates h_n of A134264 to zero except for h_0, h_3, h_6, ..., h_(3n), ... with h_0 = 1 and ultimately re-indexing. This is equivalent to recursive use of the Lagrange inversion formula on f(x) = x / h(x) = x / (1 + h_1 x + h_2 x^2 + ...) since its compositional inverse is f^{(-1)}(x) = x + N_1(h_1) x + N_2(h_1,h_2) x^2 + .... The equivalence of the two methods of generation--the substitution and the zeroing out--follows from the general theorems stated by Peter Bala in his presentation of formulas for A108767 in 2008, which stem from a fixed point-iteration formalism of a basic identity for a compositional inverse pair, x* h(f^{(-1)}(x)) = f^{(-1)}(x), where, as above, h(x) = x / f(x).

The sets of refined m-Narayana polynomials are used by Cachazo and Umbert to characterize the scattering amplitudes of a class of quantum fields (see, e.g., section 7.3).

These could also be called the refined 3-Dyck path polynomials. From the interpretation of A134264 as Dyck paths in A125181, or staircases whose steps never rise above the diagonal of a square grid (see illustrations in Weisstein), the monomials of the partition polynomial N_4 = 1 (4') + 4 (1') (3') + 2 (2')^2 + 6 (1')^2 (2') + 1 (1')^4 of A134264 have the following correspondences:

1 (4') --> 1 staircase of one step of height 4,

4 (1') (3') --> 4 staircases of 1 step of height 1 and 1 step of height 3,

2 (2')^2 --> 2 staircases of 2 steps of height 2,

6 (1')^2 (2') --> 6 staircases of 2 steps of height 1 and 1 step of height 2,

1 (1')^4 --> 1 staircase of 4 steps of height 1.

Consequently, the partition polynomials G_{3n} of this entry enumerate staircases of height 3n with steps of heights 3, 6, 9, ..., 3k, ... only.

Diverse combinatorial models of the refined m-Narayana, or m-Dyck, polynomials are inherited from those presented for the refined Narayana, or noncrossing partition, polynomials in A134264 and A125181 and in the references therein.

A127537 gives a combinatorial model (see title and Domb and Barret therein, Table 2, p. 355) that contains the coefficients of the monomials h_1^n and h_1^(n-2) h_2, i.e., A001764 and A003408.

These were formerly sometimes called Segner numbers.

A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, "Catalan Numbers", Cambridge University Press, 2015. This is probably the longest entry in the OEIS, and rightly so.

The solution to Schröder's first problem: number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]

Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - Joerg Arndt, Jul 11 2011

Noncrossing partitions are partitions of genus 0. - Robert Coquereaux, Feb 13 2024

a(n-1) is the number of ways of expressing an n-cycle (123...n) in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_iA000272. - Joerg Arndt and Greg Stevenson, Jul 11 2011

a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - Wolfdieter Lang, Aug 07 2007

As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - M. F. Hasler, Feb 22 2012

Shifts one place left when convolved with itself.

For n >= 1, a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001

Number of ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then the number of ways of forming n chords is given by (2n-1)!! = (2n)!/(n!*2^n) = A001147(n).)

Arises in Schubert calculus - see Sottile reference.

Inverse Euler transform of sequence is A022553.

With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry, Jul 18 2003

The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example: Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1. - Philippe Deléham, Mar 04 2004

a(n) equals the sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna, Apr 23 2005

Also coefficients of the Mandelbrot polynomial M iterated an infinite number of times. Examples: M(0) = 0 = 0*c^0 = [0], M(1) = c = c^1 + 0*c^0 = [1 0], M(2) = c^2 + c = c^2 + c^1 + 0*c^0 = [1 1 0], M(3) = (c^2 + c)^2 + c = [0 1 1 2 1], ... ... M(5) = [0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1], ... - Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005

The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Franklin T. Adams-Watters, Feb 08 2006

Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post, Mar 06 2006

The answer is yes. Using the formula C_n = binomial(2n,n)/(n+1), it is immediately clear that C_n can have no prime factor greater than 2n. For n >= 7, C_n > (2n)^2, so it cannot be a semiprime. Given that the Catalan numbers grow exponentially, the above consideration implies that the number of prime divisors of C_n, counted with multiplicity, must grow without limit. The number of distinct prime divisors must also grow without limit, but this is more difficult. Any prime between n+1 and 2n (exclusive) must divide C_n. That the number of such primes grows without limit follows from the prime number theorem. - Franklin T. Adams-Watters, Apr 14 2006

The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii) box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh, Dec 04 2006

a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid. - Abdullahi Umar, Aug 25 2008

a(n) is the number of trivial representations in the direct product of 2n spinor (the smallest) representations of the group SU(2) (A(1)). - Rutger Boels (boels(AT)nbi.dk), Aug 26 2008

The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - Mats Granvik, Gary W. Adamson and Roger L. Bagula, Sep 09 2008, Sep 12 2008

Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008

Starting with offset 1 = row sums of triangle A154559. - Gary W. Adamson, Jan 11 2009

C(n) is the degree of the Grassmannian G(1,n+1): the set of lines in (n+1)-dimensional projective space, or the set of planes through the origin in (n+2)-dimensional affine space. The Grassmannian is considered a subset of N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that meet all of them. - Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009

Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84, ...) convolved with Fine numbers, A000957: (1, 0, 1, 2, 6, 18, ...). a(6) = 132 = (1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. - Gary W. Adamson, May 01 2009

Convolved with A032443: (1, 3, 11, 42, 163, ...) = powers of 4, A000302: (1, 4, 16, ...). - Gary W. Adamson, May 15 2009

Sum_{k>=1} C(k-1)/2^(2k-1) = 1. The k-th term in the summation is the probability that a random walk on the integers (beginning at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. - Geoffrey Critzer, Sep 12 2009

C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009

Leonhard Euler used the formula C(n) = Product_{i=3..n} (4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - Peter Luschny, Mar 13 2010

Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - Gary W. Adamson, Jul 07 2010

a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - Christian Stump, Nov 02 2010

From Matthew Vandermast, Nov 22 2010: (Start)

Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d.

If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. (End)

Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - Jonathan Vos Post, Dec 09 2010

a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that f(1)=1 and for all n >= 1 f(n+1) <= f(n)+1. For a nice bijection between this set of functions and the set of length 2n Dyck words, see page 333 of the Fxtbook (see link below). - Geoffrey Critzer, Dec 16 2010

Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - N. J. A. Sloane, Dec 10 2011

Number of permutations in S(n) for which length equals depth. - Bridget Tenner, Feb 22 2012

a(n) is also the number of standard Young tableau of shape (n,n). - Thotsaporn Thanatipanonda, Feb 25 2012

a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - Dennis P. Walsh, Apr 11 2012

Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - Joerg Arndt, Nov 12 2012

Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012

a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - José Luis Ramírez Ramírez, Jan 16 2013

If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - Gary Detlefs, Feb 20 2013

Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013

a(n) is the size of the Jones monoid on 2n points (cf. A225798). - James Mitchell, Jul 28 2013

For 0 < p < 1, define f(p) = Sum_{n>=0} a(n)*(p*(1-p))^n, then f(p) = min{1/p, 1/(1-p)}, so f(p) reaches its maximum value 2 at p = 0.5, and p*f(p) is constant 1 for 0.5 <= p < 1. - Bob Selcoe, Nov 16 2013 [Corrected by Jianing Song, May 21 2021]

No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013

From Alexander Adamchuk, Dec 27 2013: (Start)

Prime p divides a((p+1)/2) for p > 3. See A120303(n) = Largest prime factor of Catalan number.

Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = A121839.

Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio.

3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)

For a relation to the inviscid Burgers's, or Hopf, equation, see A001764. - Tom Copeland, Feb 15 2014

From Fung Lam, May 01 2014: (Start)

One class of generalized Catalan numbers can be defined by g.f. A(x) = (1-sqrt(1-q*4*x*(1-(q-1)*x)))/(2*q*x) with nonzero parameter q. Recurrence: (n+3)*a(n+2) -2*q*(2*n+3)*a(n+1) +4*q*(q-1)*n*a(n) = 0 with a(0)=1, a(1)=1.

Asymptotic approximation for q >= 1: a(n) ~ (2*q+2*sqrt(q))^n*sqrt(2*q*(1+sqrt(q))) /sqrt(4*q^2*Pi*n^3).

For q <= -1, the g.f. defines signed sequences with asymptotic approximation: a(n) ~ Re(sqrt(2*q*(1+sqrt(q)))*(2*q+2*sqrt(q))^n) / sqrt(q^2*Pi*n^3), where Re denotes the real part. Due to Stokes' phenomena, accuracy of the asymptotic approximation deteriorates at/near certain values of n.

Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).

(End)

Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, Sum_{j=0..n} s(j) = n, and Sum_{j=0..k} s(j)-1 >= 0 for k < n-1 (and necessarily Sum_{j=0..n-1} s(j)-1 = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - Joerg Arndt, Jun 30 2014

Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - Joerg Arndt, Jul 01 2014

a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014

In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - Joachim Wuttke, Sep 11 2014

The o.g.f. C(x) = (1 - sqrt(1-4x))/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci (A000045), and Fine (A000957) numbers and polynomials (A030528), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions (A091867, connected to sums of the refined Narayana numbers A134264). - Tom Copeland, Nov 04 2014

Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015

The Catalan number series A000108(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, A000330(n+2), offset n=0 (empirical observation). - Tony Foster III, Sep 05 2016

Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give A001477, A006858, and A091962, respectively, without the first 2 terms in all cases. More generally, the Hankel transform of the Catalan numbers with the first k terms omitted is H_k(n) = Product_{j=1..k-1} Product_{i=1..j} (2*n+j+i)/(j+i) [see Cigler (2011), Eq. (1.14) and references therein]; together they form the array A078920/A123352/A368025. - Andrey Zabolotskiy, Oct 13 2016

Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. See S. J. Miller, ed., 2015, p. 5. - N. J. A. Sloane, Feb 09 2017

Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - Tom Copeland, Jul 08 2018

Let M_n be the n X n matrix with M_n(i,j) = binomial(i+j-1,2j-2); then det(M_n) = a(n). - Tony Foster III, Aug 30 2018

Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - N. J. A. Sloane, Dec 25 2018

Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - Noah A Rosenberg, Jan 28 2019

Finding solutions of eps*x^2+x-1 = 0 for eps small, that is, writing x = Sum_{n>=0} x_{n}*eps^n and expanding, one finds x = 1 - eps + 2*eps^2 - 5*eps^3 + 14*eps^3 - 42*eps^4 + ... with x_{n} = (-1)^n*C(n). Further, letting x = 1/y and expanding y about 0 to find large roots, that is, y = Sum_{n>=1} y_{n}*eps^n, one finds y = 0 - eps + eps^2 - 2*eps^3 + 5*eps^3 - ... with y_{n} = (-1)^n*C(n-1). - Derek Orr, Mar 15 2019

Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - Elise Anderson, R. M. Argus, Caitlin Owens, Tessa Stevens, Jun 27 2019

For n > 0, a random selection of n + 1 objects (the minimum number ensuring one pair by the pigeonhole principle) from n distinct pairs of indistinguishable objects contains only one pair with probability 2^(n-1)/a(n) = b(n-1)/A098597(n), where b is the 0-offset sequence with the terms of A120777 repeated (1,1,4,4,8,8,64,64,128,128,...). E.g., randomly selecting 6 socks from 5 pairs that are black, blue, brown, green, and white, results in only one pair of the same color with probability 2^(5-1)/a(5) = 16/42 = 8/21 = b(4)/A098597(5). - Rick L. Shepherd, Sep 02 2019

See Haran & Tabachnikov link for a video discussing Conway-Coxeter friezes. The Conway-Coxeter friezes with n nontrivial rows are generated by the counts of triangles at each vertex in the triangulations of regular n-gons, of which there are a(n). - Charles R Greathouse IV, Sep 28 2019

For connections to knot theory and scattering amplitudes from Feynman diagrams, see Broadhurst and Kreimer, and Todorov. Eqn. 6.12 on p. 130 of Bessis et al. becomes, after scaling, -12g * r_0(-y/(12g)) = (1-sqrt(1-4y))/2, the o.g.f. (expressed as a Taylor series in Eqn. 7.22 in 12gx) given for the Catalan numbers in Copeland's (Sep 30 2011) formula below. (See also Mizera p. 34, Balduf pp. 79-80, Keitel and Bartosch.) - Tom Copeland, Nov 17 2019

Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - Bridget Tenner, Jan 16 2020

Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - Bridget Tenner, Jan 16 2020

Legendre gives the following formula for computing the square root modulo 2^m:

sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m

as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - Peter Schorn, Feb 11 2020

a(n) is the number of length n permutations sorted to the identity by a consecutive-132-avoiding stack followed by a classical-21-avoiding stack. - Kai Zheng, Aug 28 2020

Number of non-crossing partitions of a 2*n-set with n blocks of size 2. Also number of non-crossing partitions of a 2*n-set with n+1 blocks of size at most 3, and without cyclical adjacencies. The two partitions can be mapped by rotated Kreweras bijection. - Yuchun Ji, Jan 18 2021

Named by Riordan (1968, and earlier in Mathematical Reviews, 1948 and 1964) after the French and Belgian mathematician Eugène Charles Catalan (1814-1894) (see Pak, 2014). - Amiram Eldar, Apr 15 2021

For n >= 1, a(n-1) is the number of interpretations of x^n is an algebra where power-associativity is not assumed. For example, for n = 4 there are a(3) = 5 interpretations: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x. See the link "Non-associate powers and a functional equation" from I. M. H. Etherington and the page "Nonassociative Product" from Eric Weisstein's World of Mathematics for detailed information. See also A001190 for the case where multiplication is commutative. - Jianing Song, Apr 29 2022

Number of states in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - Andrea Arlette España, Nov 06 2022

a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - Juan B. Gil, Jun 22 2023

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

a(n) is the number of extremely lucky Stirling permutations of order n; i.e., the number of Stirling permutations of order n that have exactly n lucky cars. (see Colmenarejo et al. reference) - Bridget Tenner, Apr 16 2024

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

Number of antichains (or order ideals) in the poset 2*(k-1)*(n-k) or plane partitions with rows <= k-1, columns <= n-k and entries <= 2. - Mitch Harris, Jul 15 2000

T(n,k) is the number of Dyck n-paths with exactly k peaks. a(n,k) = number of pairs (P,Q) of lattice paths from (0,0) to (k,n+1-k), each consisting of unit steps East or North, such that P lies strictly above Q except at the endpoints. - David Callan, Mar 23 2004

Number of permutations of [n] which avoid-132 and have k-1 descents. - Mike Zabrocki, Aug 26 2004

T(n,k) is the number of paths through n panes of glass, entering and leaving from one side, of length 2n with k reflections (where traversing one pane of glass is the unit length). - Mitch Harris, Jul 06 2006

Antidiagonal sums given by A004148 (without first term).

T(n,k) is the number of full binary trees with n internal nodes and k-1 jumps. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007

From Gary W. Adamson, Oct 22 2007: (Start)

The n-th row can be generated by the following operation using an ascending row of (n-1) triangular terms, (A) and a descending row, (B); e.g., row 6:

A: 1....3....6....10....15

B: 15...10....6.....3.....1

C: 1...15...50....50....15....1 = row 6.

Leftmost column of A,B -> first two terms of C; then followed by the operation B*C/A of current column = next term of row C, (e.g., 10*15/3 = 50). Continuing with the operation, we get row 6: (1, 15, 50, 50, 15, 1). (End)

The previous comment can be upgraded to: The ConvOffsStoT transform of the triangular series; and by rows, row 6 is the ConvOffs transform of (1, 3, 6, 10, 15). Refer to triangle A117401 as another example of the ConvOffsStoT transform, and OEIS under Maple Transforms. - Gary W. Adamson, Jul 09 2012

For a connection to Lagrange inversion, see A134264. - Tom Copeland, Aug 15 2008

T(n,k) is also the number of order-decreasing and order-preserving mappings (of an n-element set) of height k (height of a mapping is the cardinal of its image set). - Abdullahi Umar, Aug 21 2008

Row n of this triangle is the h-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p.60]. See A033282 for the corresponding array of f-vectors for associahedra of type A_n. See A008459 and A145903 for the h-vectors for associahedra of type B and type D respectively. The Hilbert transform of this triangle (see A145905 for the definition of this transform) is A145904. - Peter Bala, Oct 27 2008

T(n,k) is also the number of noncrossing set partitions of [n] into k blocks. Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings. - Peter Luschny, Apr 29 2011

Noncrossing set partitions are also called genus 0 partitions. In terms of genus-dependent Stirling numbers of the second kind S2(n,k,g) that count partitions of genus g of an n-set into k nonempty subsets, one has T(n,k) = S2(n,k,0). - Robert Coquereaux, Feb 15 2024

Diagonals of A089732 are rows of A001263. - Tom Copeland, May 14 2012

From Peter Bala, Aug 07 2013: (Start)

Let E(y) = Sum_{n >= 0} y^n/(n!*(n+1)!) = 1/sqrt(y)*BesselI(1,2*sqrt(y)). Then this triangle is the generalized Riordan array (E(y), y) with respect to the sequence n!*(n+1)! as defined in Wang and Wang.

Generating function E(y)*E(x*y) = 1 + (1 + x)*y/(1!*2!) + (1 + 3*x + x^2)*y^2/(2!*3!) + (1 + 6*x + 6*x^2 + x^3)*y^3/(3!*4!) + .... Cf. A105278 with a generating function exp(y)*E(x*y).

The n-th power of this array has a generating function E(y)^n*E(x*y). In particular, the matrix inverse A103364 has a generating function E(x*y)/E(y). (End)

T(n,k) is the number of nonintersecting n arches above the x axis, starting and ending on vertices 1 to 2n, with k being the number of arches starting on an odd vertice and ending on a higher even vertice. Example: T(3,2)=3 [16,25,34] [14,23,56] [12,36,45]. - Roger Ford, Jun 14 2014

Fomin and Reading on p. 31 state that the rows of the Narayana matrix are the h-vectors of the associahedra as well as its dual. - Tom Copeland, Jun 27 2017

The row polynomials P(n, x) = Sum_{k=1..n} T(n, k)*x^(k-1), together with P(0, x) = 1, multiplied by (n+1) are the numerator polynomials of the o.g.f.s of the diagonal sequences of the triangle A103371: G(n, x) = (n+1)*P(n, x)/(1 - x)^{2*n+1}, for n >= 0. This is proved with Lagrange's theorem applied to the Riordan triangle A135278 = (1/(1 - x)^2, x/(1 - x)). See an example below. - Wolfdieter Lang, Jul 31 2017

T(n,k) is the number of Dyck paths of semilength n with k-1 uu-blocks (pairs of consecutive up-steps). - Alexander Burstein, Jun 22 2020

In case you were searching for Narayama numbers, the correct spelling is Narayana. - N. J. A. Sloane, Nov 11 2020

Named after the Canadian mathematician Tadepalli Venkata Narayana (1930-1987). They were also called "Runyon numbers" after John P. Runyon (1922-2013) of Bell Telephone Laboratories, who used them in a study of a telephone traffic system. - Amiram Eldar, Apr 15 2021 The Narayana numbers were first studied by Percy Alexander MacMahon (see reference, Article 495) as pointed out by Bóna and Sagan (see link). - Peter Luschny, Apr 28 2022

From Andrea Arlette España, Nov 14 2022: (Start)

T(n,k) is the degree distribution of the paths towards synchronization in the transition diagram associated with the Laplacian system over the complete graph K_n, corresponding to ordered initial conditions x_1 < x_2 < ... < x_n.

T(n,k) for n=2N+1 and k=N+1 is the number of states in the transition diagram associated with the Laplacian system over the complete bipartite graph K_{N,N}, corresponding to ordered (x_1 < x_2 < ... < x_N and x_{N+1} < x_{N+2} < ... < x_{2N}) and balanced (Sum_{i=1..N} x_i/N = Sum_{i=N+1..2N} x_i/N) initial conditions. (End)

From Gus Wiseman, Jan 23 2023: (Start)

Also the number of unlabeled ordered rooted trees with n nodes and k leaves. See the link by Marko Riedel. For example, row n = 5 counts the following trees:

((((o)))) (((o))o) ((o)oo) (oooo)

(((o)o)) ((oo)o)

(((oo))) ((ooo))

((o)(o)) (o(o)o)

((o(o))) (o(oo))

(o((o))) (oo(o))

The unordered version is A055277. Leaves in standard ordered trees are counted by A358371. (End)

The number of terms in the n-th row is the number of partitions of n, A000041(n). - Amarnath Murthy, Sep 21 2002

For each n, the partitions are ordered according to A-St: first by length and then lexicographically (arranging the parts in nondecreasing order), which is different from the usual practice of ordering all partitions lexicographically. - T. D. Noe, Nov 03 2006

For this ordering of the partitions, for n >= 1, see the remarks and the C. F. Hindenburg link given in A036036. - Wolfdieter Lang, Jun 15 2012

The relation (n+1) * A134264(n+1) = A248120(n+1) / a(n) where the arithmetic is performed for matching partitions in each row n connects the combinatorial interpretations of this array to some topological and algebraic constructs of the two other entries. Also, these seem (cf. MOPS reference, Table 2) to be the coefficients of the Jack polynomial J(x;k,alpha=0). - Tom Copeland, Nov 24 2014

The conjecture on the Jack polynomials of zero order is true as evident from equation a) on p. 80 of the Stanley reference, suggested to me by Steve Kass. The conventions for denoting the more general Jack polynomials J(n,alpha) vary. Using Stanley's convention, these Jack polynomials are the umbral extensions of the multinomial expansion of (s_1*x_1 + s_2*x_2 + ... + s_(n+1)*x_(n+1))^n in which the subscripts of the (s_k)^j in the symmetric monomial expansions are finally ignored and the exponent dropped to give s_j(alpha) = j-th row polynomial of A094638 or |A008276| in ascending powers of alpha. (The MOPS table has some inconsistency between n = 3 and n = 4.) - Tom Copeland, Nov 26 2016

T(n,k) is the number of subsets of {1,2,...,n-1} of size k and containing no consecutive integers. Example: T(6,2)=6 because the subsets of size 2 of {1,2,3,4,5} with no consecutive integers are {1,3},{1,4},{1,5},{2,4},{2,5} and {3,5}. Equivalently, T(n,k) is the number of k-matchings of the path graph P_n. - Emeric Deutsch, Dec 10 2003

T(n,k) = number of compositions of n+2 into k+1 parts, all >= 2. Example: T(6,2)=6 because we have (2,2,4),(2,4,2),(4,2,2),(2,3,3),(3,2,3) and (3,3,2). - Emeric Deutsch, Apr 09 2005

Given any recurrence sequence S(k) = x*a(k-1) + a(k-2), starting (1, x, x^2+1, ...); the (k+1)-th term of the series = f(x) in the k-th degree polynomial: (1, (x), (x^2 + 1), (x^3 + 2x), (x^4 + 3x^2 + 1), (x^5 + 4x^3 + 3x), (x^6 + 5x^4 + 6x^2 + 1), ...). Example: let x = 2, then S(k) = 1, 2, 5, 12, 29, 70, 169, ... such that A000129(7) = 169 = f(x), x^6 + 5x^4 + 6x^2 + 1 = (64 + 80 + 24 + 1). - Gary W. Adamson, Apr 16 2008

Row k gives the nonzero coefficients of U(k,x/2) where U is the Chebyshev polynomial of the second kind. For example, row 6 is 1,5,6,1 and U(6,x/2) = x^6 - 5x^4 + 6x^2 - 1. - David Callan, Jul 22 2008

T(n,k) is the number of nodes at level k in the Fibonacci tree f(k-1). The Fibonacci trees f(k) of order k are defined as follows: 1. f(-1) and f(0) each consist of a single node. 2. For k >= 1, to the root of f(k-1), taken as the root of f(k), we attach with a rightmost edge the tree f(k-2). See the Iyer and Reddy references. These trees are not the same as the Fibonacci trees in A180566. Example: T(3,0)=1 and T(3,1)=2 because in f(2) = /\ we have 1 node at level 0 and 2 nodes at level 1. - Emeric Deutsch, Jun 21 2011

Triangle, with zeros omitted, given by (1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2011

Riordan array (1/(1-x),x^2/(1-x). - Philippe Deléham, Dec 12 2011

This sequence is the elements on the rising diagonals of the Pascal triangle, where the sum of the elements in each rising diagonal represents a Fibonacci number. - Mohammad K. Azarian, Mar 08 2012

If we set F(0;x) = 0, F(1;x) = 1, F(n+1;x) = x*F(n;x) + F(n-1;x), then we obtain the sequence of Vieta-Fibonacci polynomials discussed by Gary W. Adamson above. We note that F(n;x) = (-i)^n * U(n;i*x/2), where U denotes the respective Chebyshev polynomial of the second kind (see David Callan's remark above). Let us fix a,b,f(0),f(1) in C, b is not the zero, and set f(n) = a*f(n-1) + b*f(n-2). Then we deduce the relation: f(n) = b^((n-1)/2) * F(n;a/sqrt(b))*f(1) + b^(n/2) * F(n-1;a/sqrt(b))*f(0), where for a given value of the complex root sqrt(b) we set b^(n/2) = (sqrt(b))^n. Moreover, if b=1 then we get f(n+k) + (-1)^k * f(n-k) = L(k;a)*f(n), for every k=0,1,...,n, and where L(0;a)=2, L(1;a)=a, L(n+1;a)=a*L(n;a) + L(n-1;a) are the Vieta-Lucas polynomials. Let us observe that L(n+2;a) = F(n+2;a) + F(n;a), L(m+n;a) = L(m;a)*F(n;a) + L(m-1;a)*F(n-1;a), which implies also L(n+1;a) = a*F(n;a) + 2*F(n-1;a). Further we have L(n;a) = 2*(-i)^n * T(n;i*x/2), where T(n;x) denotes the n-th Chebyshev polynomial of the first kind. For the proofs, other relations and facts - see Witula-Slota's papers. - Roman Witula, Oct 12 2012

The diagonal sums of this triangle are A000930. - John Molokach, Jul 04 2013

Aside from signs and index shift, the coefficients of the characteristic polynomial of the Coxeter adjacency matrix for the Coxeter group A_n related to the Chebyshev polynomial of the second kind (cf. Damianou link p. 19). - Tom Copeland, Oct 11 2014

For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. - Tom Copeland, Nov 04 2014

For a relation to a formulation for a universal Lie Weyl algebra for su(1,1), see page 16 of Durov et al. - Tom Copeland, Nov 29 2014

A reversed, signed and aerated version is given by A049310, related to Chebyshev polynomials. - Tom Copeland, Dec 06 2015

For n >= 3, the n-th row gives the coefficients of the independence polynomial of the (n-2)-path graph P_{n-2}. - Eric W. Weisstein, Apr 07 2017

For n >= 2, the n-th row gives the coefficients of the matching-generating polynomial of the (n-1)-path graph P_{n-1}. - Eric W. Weisstein, Apr 10 2017

Antidiagonals of the Pascal matrix A007318 read bottom to top. These are also the antidiagonals read from top to bottom of the numerical coefficients of the Maurer-Cartan form matrix of the Leibniz group L^(n)(1,1) presented on p. 9 of the Olver paper), which is generated as exp[c. * M] with (c.)^n = c_n and M the Lie infinitesimal generator A218272. Reverse is A102426. - Tom Copeland, Jul 02 2018

T(n,k) is the number of Markov equivalence classes with skeleton the path on n+1 nodes having exactly k immoralities. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018

T(n, k) = number of compositions of n+1 into n+1-2*k odd parts. For example, T(6,2) = 6 because 7 = 5+1+1 = 3+3+1 = 3+1+3 = 1+1+5 = 1+3+3 = 1+1+5. - Michael Somos, Sep 19 2019

From Gary W. Adamson, Apr 25 2022: (Start)

Alternate rows can be parsed into those with odd integer coefficients to the right of the leftmost 1, and those with even integer coefficients to the right of the leftmost 1. The first set is shown in A054142 and are characteristic polynomials of submatrices of an infinite tridiagonal matrix (A332602) with all -1's in the super and subdiagonals and (1,2,2,2,...) as the main diagonal. For example, the characteristic equation of the 3 X 3 submatrix (1,-1,0; -1,2,-1; 0,-1,2) is x^3 - 5x^2 + 6x - 1. The roots are the Beraha constants B(7,1) = 3.24697...; B(7,2) = 1.55495...; and B(7,3) = 0.198062.... For n X n matrices of this form, the largest eigenvalue is B(2n+1, 1). The 3 X 3 matrix has an eigenvalue of 3.24697... = B(7,1).

Polynomials with even integer coefficients to the right of the leftmost 1 are in A053123 with roots being the even-indexed Beraha constants. The generating Cartan matrices are those with (2,2,2,...) as the main diagonal and -1's as the sub- and superdiagonals. The largest eigenvalue of n X n matrices of this form are B(2n+2,1). For example, the largest eigenvalue of (2,-1,0; -1,2,-1; 0,-1,2) is 3.414... = B(8,1) = a root to x^3 - 6x^2 + 10x - 4. (End)

T(n,k) is the number of edge covers of P_(n+2) with (n-k) edges. For example, T(6,2)=6 because among edges 1, 2, ..., 7 of P_8, we can eliminate any two non-consecutive edges among 2-6. These numbers can be found using the recurrence relation for the edge cover polynomial of P_n, which is E(P_n,x) = xE(P_(n-1),x)+xE(P_(n-2),x) and E(P_1,x)=0, E(P_2,x)=x (ref. Akbari and Oboudi). - Feryal Alayont, Jun 03 2022

T(n,k) is the number of ways to tile an n-board (an n X 1 array of 1 X 1 cells) using k dominoes and n-2*k squares. - Michael A. Allen, Dec 28 2022

T(n,k) is the number of positive integer sequences (s(1),s(2),...,s(n-2k)) such that s(i) < s(i+1), s(1) is odd, s(n-2k) <= n, and s(i) and s(i+1) have opposite parity (ref. Donnelly, Dunkum, and McCoy). Example: T(6,0)=1 corresponds to 123456; T(6,1)=5 corresponds to 1234, 1236, 1256, 1456, 3456; T(6,2)=6 corresponds to 12, 14, 16, 34, 36; and T(6,3)=1 corresponds to the empty sequence () with length 0. - Molly W. Dunkum, Jun 27 2023

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)