cp's OEIS Frontend

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

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

a(n+2) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A000110(k) for k = 0, 1, ..., n. - Michael Somos, Oct 07 2003

Number of complete rhyming schemes.

Whereas the Bell number B(n) (A000110(n)) is the number of terms in the polynomial that expresses the n-th moment of a probability distribution as a function of the first n cumulants, these numbers give the number of terms in the corresponding expansion of the central moment as a function of the first n cumulants. - Michael Hardy (hardy(AT)math.umn.edu), Jan 26 2005

a(n) is the number of permutations on [n] for which the left-to-right maxima coincide with the descents (entries followed by a smaller number). For example, a(4) counts 2143, 3142, 3241, 4123. - David Callan, Jul 20 2005

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of stable partitions of an n-cycle, where a stable partition of a graph is a set partition of the vertex set such that no edge has both ends in the same block. A bijective proof is given in David Callan's article. For example, the a(5) = 11 stable partitions are:

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

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

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

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

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

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

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

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

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

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

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

(End)

Also number of partitions of {1, 2, ..., n-1} with singletons. E.g., a(4) = 4: {1|2|3, 12|3, 13|2, 1|23}. Also number of cyclical adjacencies partitions of {1, 2, ..., n-1}. E.g., a(4) = 4: {12|3, 13|2, 1|23, 123}. The two partitions can be mapped by a Kreweras bijection. - Yuchun Ji, Feb 22 2021

Also the k-th central moment of a Poisson random variable with mean 1. a(n) = E[(X-1)^n, X~Poisson(1)]. - Thomas Dybdahl Ahle, Dec 14 2022

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)

...B...C.......A...B

....\./.........\./

.A...x....-->....x...C.................A..().........()..A..

..\./.............\./...................\./....-->....\./...

...x...............x.....................x.............x....

(a . (b . c)) -> ((a . b) . c) ____ (a . ()) --> (() . a)

That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.

This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)

A...B..............B...C

.\./................\./

..x...C..-->.....A...x................()..B.......B..()

...\./............\./..................\./...-->...\./.

....x..............x....................x...........x..

((a . b) . c) -> (a . (b . c)) __ (() . b) --> (b . ())

That is, we rotate the binary tree right, in case it is possible and otherwise (if the left hand side of a tree is a terminal node) swap the right and left subtree (so that the terminal node ends to the right hand side), i.e. apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.

See also the comments at A074679.

Also a(n) is the number of hexaflexagons of order n+2. - Mike Godfrey (m.godfrey(AT)umist.ac.uk), Feb 25 2002 (see the Kosters paper).

Number of normally non-isomorphic realizations of the associahedron of type II with dimension n in Ceballos et al. - Tom Copeland, Oct 19 2011

Number of polyforms with n cells in the hyperbolic tiling with Schläfli symbol {3,oo}, not distinguishing enantiomorphs. - Thomas Anton, Jan 16 2019

A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 20 2024

A maximal outerplanar graph (MOP) has a plane embedding with all vertices on the exterior region and interior regions triangles. - Allan Bickle, Feb 25 2024

Also arises in enumeration of stereoisomers of alkane systems.

"A simplicial d-cluster may be informally described as being constructed by gluing regular d-simplexes together facet-by-facet, at each stage gluing a new simplex to exactly one facet of a cluster already constructed. The equivalence classes of such clusters under rigid motions are in one-to-one correspondence with the combinatorial types of stack polytopes." [Hering et al., 1982] - Jonathan Vos Post, Apr 22 2011

The Hering article has an error in the 14th term. - Robert A. Russell, Apr 11 2012

Also same as A027610 with mirror-image not treated as equivalence. - Brendan McKay, Mar 08 2014

Number of oriented polyominoes composed of n tetrahedral cells of the hyperbolic regular tiling with Schläfli symbol {3,3,oo}. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Mar 20 2024

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated counterclockwise.

The number of cycles in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+2), otherwise the same sequence as for Catalan bijections *A074679/*A074680, but shifted once left (for an explanation, see the related notes in OEIS Wiki).

E.g., in range [A014137(0)..A014138(1)] = [1,1] there is one cycle (as a(1)=1), in range [A014137(1)..A014138(2)] = [2,3] there is one cycle (as a(2)=3 and a(3)=2), in range [A014137(2)..A014138(3)] = [4,8] there is also one cycle (as a(4) = 7, a(7) = 6, a(6) = 5, a(5) = 8 and a(8) = 4), and in range [A014137(3)..A014138(4)] = [9,22] there are A001683(4+2) = 4 cycles.

From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505 by the same method, when the other side of the formula is also "recursivized".

Also, with a different offset, number of colored quivers in the 2-mutation class of a quiver of Dynkin type A_n. - N. J. A. Sloane, Jan 22 2013

Closed formula is given in my paper linked below. - Nikos Apostolakis, Aug 01 2018

Number of oriented polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 20 2024