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

2^0 = 1 is the only odd power of 2.

Number of subsets of an n-set.

There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.

This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]

Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003

a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.

Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.

With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson

Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004

Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]

Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.

The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.

The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).

The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005

With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005

The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.

The first differences are the sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005

a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006

Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006

For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007

Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008

a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008

2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008

a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008

Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008

A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n) = A000079 leads to 2, 1, 8, 4, 32, 16, ... = A135520. - Paul Curtz, Jan 05 2009

This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009

a(n) = a(n-1)-th even natural number (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009

For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009

Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009

Catalan transform of A099087. - R. J. Mathar, Jun 29 2009

a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009

Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009

These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009

A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - Reinhard Zumkeller, Feb 08 2010

a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010

a(n) is the smallest proper multiple of a(n-1). - Dominick Cancilla, Aug 09 2010

The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010

Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011

Row sums of A152538. - Gary W. Adamson, Dec 10 2008

A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 2011

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011

Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011

The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011

a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012

A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012

For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012

First differences of A000225. - Omar E. Pol, Feb 19 2013

This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013

a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013

Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013

More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013

Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013

Numbers n such that sigma(2n) = 2n + sigma(n). - Jahangeer Kholdi, Nov 23 2013

a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013

Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013

A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014

a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014

If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014

The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014

The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014

a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014

Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht, Aug 14 2014

This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014

a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014

a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015

b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015

a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015

a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015

Subsequence of A028982 (the squares or twice squares sequence). - Timothy L. Tiffin, Jul 18 2016

A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - Juri-Stepan Gerasimov, Aug 16 2016

Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016

Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016

Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017

Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017

Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017

Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018

The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018

k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019

Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - M. Farrokhi D. G., Jan 03 2020

a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020

a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021

For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023

Devadoss refers to these numbers as type B Catalan numbers (cf. A000108).

Equal to the binomial coefficient sum Sum_{k=0..n} binomial(n,k)^2.

Number of possible interleavings of a program with n atomic instructions when executed by two processes. - Manuel Carro (mcarro(AT)fi.upm.es), Sep 22 2001

Convolving a(n) with itself yields A000302, the powers of 4. - T. D. Noe, Jun 11 2002

Number of ordered trees with 2n+1 edges, having root of odd degree and nonroot nodes of outdegree 0 or 2. - Emeric Deutsch, Aug 02 2002

Also number of directed, convex polyominoes having semiperimeter n+2.

Also number of diagonally symmetric, directed, convex polyominoes having semiperimeter 2n+2. - Emeric Deutsch, Aug 03 2002

The second inverse binomial transform of this sequence is this sequence with interpolated zeros. Its g.f. is (1 - 4*x^2)^(-1/2), with n-th term C(n,n/2)(1+(-1)^n)/2. - Paul Barry, Jul 01 2003

Number of possible values of a 2n-bit binary number for which half the bits are on and half are off. - Gavin Scott (gavin(AT)allegro.com), Aug 09 2003

Ordered partitions of n with zeros to n+1, e.g., for n=4 we consider the ordered partitions of 11110 (5), 11200 (30), 13000 (20), 40000 (5) and 22000 (10), total 70 and a(4)=70. See A001700 (esp. Mambetov Bektur's comment). - Jon Perry, Aug 10 2003

Number of nondecreasing sequences of n integers from 0 to n: a(n) = Sum_{i_1=0..n} Sum_{i_2=i_1..n}...Sum_{i_n=i_{n-1}..n}(1). - J. N. Bearden (jnb(AT)eller.arizona.edu), Sep 16 2003

Number of peaks at odd level in all Dyck paths of semilength n+1. Example: a(2)=6 because we have U*DU*DU*D, U*DUUDD, UUDDU*D, UUDUDD, UUU*DDD, where U=(1,1), D=(1,-1) and * indicates a peak at odd level. Number of ascents of length 1 in all Dyck paths of semilength n+1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(2)=6 because we have uDuDuD, uDUUDD, UUDDuD, UUDuDD, UUUDDD, where an ascent of length 1 is indicated by a lower case letter. - Emeric Deutsch, Dec 05 2003

a(n-1) = number of subsets of 2n-1 distinct elements taken n at a time that contain a given element. E.g., n=4 -> a(3)=20 and if we consider the subsets of 7 taken 4 at a time with a 1 we get (1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256, 1257, 1267, 1345, 1346, 1347, 1356, 1357, 1367, 1456, 1457, 1467, 1567) and there are 20 of them. - Jon Perry, Jan 20 2004

The dimension of a particular (necessarily existent) absolutely universal embedding of the unitary dual polar space DSU(2n,q^2) where q>2. - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.

Number of standard tableaux of shape (n+1, 1^n). - Emeric Deutsch, May 13 2004

Erdős, Graham et al. conjectured that a(n) is never squarefree for sufficiently large n (cf. Graham, Knuth, Patashnik, Concrete Math., 2nd ed., Exercise 112). Sárközy showed that if s(n) is the square part of a(n), then s(n) is asymptotically (sqrt(2)-2) * (sqrt(n)) * zeta(1/2). Granville and Ramare proved that the only squarefree values are a(1)=2, a(2)=6 and a(4)=70. - Jonathan Vos Post, Dec 04 2004 [For more about this conjecture, see A261009. - N. J. A. Sloane, Oct 25 2015]

The MathOverflow link contains the following comment (slightly edited): The Erdős squarefree conjecture (that a(n) is never squarefree for n>4) was proved in 1980 by Sárközy, A. (On divisors of binomial coefficients. I. J. Number Theory 20 (1985), no. 1, 70-80.) who showed that the conjecture holds for all sufficiently large values of n, and by A. Granville and O. Ramaré (Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73-107) who showed that it holds for all n>4. - Fedor Petrov, Nov 13 2010. [From N. J. A. Sloane, Oct 29 2015]

p divides a((p-1)/2)-1=A030662(n) for prime p=5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ... = A002144(n) Pythagorean primes: primes of form 4n+1. - Alexander Adamchuk, Jul 04 2006

The number of direct routes from my home to Granny's when Granny lives n blocks south and n blocks east of my home in Grid City. To obtain a direct route, from the 2n blocks, choose n blocks on which one travels south. For example, a(2)=6 because there are 6 direct routes: SSEE, SESE, SEES, EESS, ESES and ESSE. - Dennis P. Walsh, Oct 27 2006

Inverse: With q = -log(log(16)/(pi a(n)^2)), ceiling((q + log(q))/log(16)) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 26 2007

Number of partitions with Ferrers diagrams that fit in an n X n box (including the empty partition of 0). Example: a(2) = 6 because we have: empty, 1, 2, 11, 21 and 22. - Emeric Deutsch, Oct 02 2007

So this is the 2-dimensional analog of A008793. - William Entriken, Aug 06 2013

The number of walks of length 2n on an infinite linear lattice that begins and ends at the origin. - Stefan Hollos (stefan(AT)exstrom.com), Dec 10 2007

The number of lattice paths from (0,0) to (n,n) using steps (1,0) and (0,1). - Joerg Arndt, Jul 01 2011

Integral representation: C(2n,n)=1/Pi Integral [(2x)^(2n)/sqrt(1 - x^2),{x,-1, 1}], i.e., C(2n,n)/4^n is the moment of order 2n of the arcsin distribution on the interval (-1,1). - N-E. Fahssi, Jan 02 2008

Also the Catalan transform of A000079. - R. J. Mathar, Nov 06 2008

Straub, Amdeberhan and Moll: "... it is conjectured that there are only finitely many indices n such that C_n is not divisible by any of 3, 5, 7 and 11." - Jonathan Vos Post, Nov 14 2008

Equals INVERT transform of A081696: (1, 1, 3, 9, 29, 97, 333, ...). - Gary W. Adamson, May 15 2009

Also, in sports, the number of ordered ways for a "Best of 2n-1 Series" to progress. For example, a(2) = 6 means there are six ordered ways for a "best of 3" series to progress. If we write A for a win by "team A" and B for a win by "team B" and if we list the played games chronologically from left to right then the six ways are AA, ABA, BAA, BB, BAB, and ABB. (Proof: To generate the a(n) ordered ways: Write down all a(n) ways to designate n of 2n games as won by team A. Remove the maximal suffix of identical letters from each of these.) - Lee A. Newberg, Jun 02 2009

Number of n X n binary arrays with rows, considered as binary numbers, in nondecreasing order, and columns, considered as binary numbers, in nonincreasing order. - R. H. Hardin, Jun 27 2009

Hankel transform is 2^n. - Paul Barry, Aug 05 2009

It appears that a(n) is also the number of quivers in the mutation class of twisted type BC_n for n>=2.

Central terms of Pascal's triangle: a(n) = A007318(2*n,n). - Reinhard Zumkeller, Nov 09 2011

Number of words on {a,b} of length 2n such that no prefix of the word contains more b's than a's. - Jonathan Nilsson, Apr 18 2012

From Pascal's triangle take row(n) with terms in order a1,a2,..a(n) and row(n+1) with terms b1,b2,..b(n), then 2*(a1*b1 + a2*b2 + ... + a(n)*b(n)) to get the terms in this sequence. - J. M. Bergot, Oct 07 2012. For example using rows 4 and 5: 2*(1*(1) + 4*(5) + 6*(10) + 4*(10) + 1*(5)) = 252, the sixth term in this sequence.

Take from Pascal's triangle row(n) with terms b1, b2, ..., b(n+1) and row(n+2) with terms c1, c2, ..., c(n+3) and find the sum b1*c2 + b2*c3 + ... + b(n+1)*c(n+2) to get A000984(n+1). Example using row(3) and row(5) gives sum 1*(5)+3*(10)+3*(10)+1*(5) = 70 = A000984(4). - J. M. Bergot, Oct 31 2012

a(n) == 2 mod n^3 iff n is a prime > 3. (See Mestrovic link, p. 4.) - Gary Detlefs, Feb 16 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. In general, for any integer m>1 and n>0, the polynomial f_{m,n}(x) = Sum_{k=0..n} (m*k)!/(k!)^m*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013

This comment generalizes the comment dated Oct 31 2012 and the second of the sequence's original comments. For j = 1 to n, a(n) = Sum_{k=0..j} C(j,k)* C(2n-j, n-k) = 2*Sum_{k=0..j-1} C(j-1,k)*C(2n-j, n-k). - Charlie Marion, Jun 07 2013

The differences between consecutive terms of the sequence of the quotients between consecutive terms of this sequence form a sequence containing the reciprocals of the triangular numbers. In other words, a(n+1)/a(n)-a(n)/a(n-1) = 2/(n*(n+1)). - Christian Schulz, Jun 08 2013

Number of distinct strings of length 2n using n letters A and n letters B. - Hans Havermann, May 07 2014

From Fung Lam, May 19 2014: (Start)

Expansion of G.f. A(x) = 1/(1+q*x*c(x)), where parameter q is positive or negative (except q=-1), and c(x) is the g.f. of A000108 for Catalan numbers. The case of q=-1 recovers the g.f. of A000108 as xA^2-A+1=0. The present sequence A000984 refers to q=-2. Recurrence: (1+q)*(n+2)*a(n+2) + ((q*q-4*q-4)*n + 2*(q*q-q-1))*a(n+1) - 2*q*q*(2*n+1)*a(n) = 0, a(0)=1, a(1)=-q. Asymptotics: a(n) ~ ((q+2)/(q+1))*(q^2/(-q-1))^n, q<=-3, a(n) ~ (-1)^n*((q+2)/(q+1))*(q^2/(q+1))^n, q>=5, and a(n) ~ -Kq*2^(2*n)/sqrt(Pi*n^3), where the multiplicative constant Kq is given by K1=1/9 (q=1), K2=1/8 (q=2), K3=3/25 (q=3), K4=1/9 (q=4). These formulas apply to existing sequences A126983 (q=1), A126984 (q=2), A126982 (q=3), A126986 (q=4), A126987 (q=5), A127017 (q=6), A127016 (q=7), A126985 (q=8), A127053 (q=9), and to A007854 (q=-3), A076035 (q=-4), A076036 (q=-5), A127628 (q=-6), A126694 (q=-7), A115970 (q=-8). (End)

a(n)*(2^n)^(j-2) equals S(n), where S(n) is the n-th number in the self-convolved sequence which yields the powers of 2^j for all integers j, n>=0. For example, when n=5 and j=4, a(5)=252; 252*(2^5)^(4-2) = 252*1024 = 258048. The self-convolved sequence which yields powers of 16 is {1, 8, 96, 1280, 17920, 258048, ...}; i.e., S(5) = 258048. Note that the convolved sequences will be composed of numbers decreasing from 1 to 0, when j<2 (exception being j=1, where the first two numbers in the sequence are 1 and all others decreasing). - Bob Selcoe, Jul 16 2014

The variance of the n-th difference of a sequence of pairwise uncorrelated random variables each with variance 1. - Liam Patrick Roche, Jun 04 2015

Number of ordered trees with n edges where vertices at level 1 can be of 2 colors. Indeed, the standard decomposition of ordered trees leading to the equation C = 1 + zC^2 (C is the Catalan function), yields this time G = 1 + 2zCG, from where G = 1/sqrt(1-4z). - Emeric Deutsch, Jun 17 2015

Number of monomials of degree at most n in n variables. - Ran Pan, Sep 26 2015

Let V(n, r) denote the volume of an n-dimensional sphere with radius r, then V(n, 2^n) / Pi = V(n-1, 2^n) * a(n/2) for all even n. - Peter Luschny, Oct 12 2015

a(n) is the number of sets {i1,...,in} of length n such that n >= i1 >= i2 >= ... >= in >= 0. For instance, a(2) = 6 as there are only 6 such sets: (2,2) (2,1) (2,0) (1,1) (1,0) (0,0). - Anton Zakharov, Jul 04 2016

From Ralf Steiner, Apr 07 2017: (Start)

By analytic continuation to the entire complex plane there exist regularized values for divergent sums such as:

Sum_{k>=0} a(k)/(-2)^k = 1/sqrt(3).

Sum_{k>=0} a(k)/(-1)^k = 1/sqrt(5).

Sum_{k>=0} a(k)/(-1/2)^k = 1/3.

Sum_{k>=0} a(k)/(1/2)^k = -1/sqrt(7)i.

Sum_{k>=0} a(k)/(1)^k = -1/sqrt(3)i.

Sum_{k>=0} a(k)/2^k = -i. (End)

Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j). [Martinez and Savage, 2.18] - Eric M. Schmidt, Jul 17 2017

The o.g.f. for the sequence equals the diagonal of any of the following the rational functions: 1/(1 - (x + y)), 1/(1 - (x + y*z)), 1/(1 - (x + x*y + y*z)) or 1/(1 - (x + y + y*z)). - Peter Bala, Jan 30 2018

From Colin Defant, Sep 16 2018: (Start)

Let s denote West's stack-sorting map. a(n) is the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 231, and 321. a(n) is also the number of permutations pi of [n+1] such that s(pi) avoids the patterns 132, 312, and 321.

a(n) is the number of permutations of [n+1] that avoid the patterns 1342, 3142, 3412, and 3421. (End)

All binary self-dual codes of length 4n, for n>0, must contain at least a(n) codewords of weight 2n. More to the point, there will always be at least one, perhaps unique, binary self-dual code of length 4n that will contain exactly a(n) codewords that have a hamming weight equal to half the length of the code (2n). This code can be constructed by direct summing the unique binary self-dual code of length 2 (up to permutation equivalence) to itself an even number of times. A permutation equivalent code can be constructed by augmenting two identity matrices of length 2n together. - Nathan J. Russell, Nov 25 2018

From Isaac Saffold, Dec 28 2018: (Start)

Let [b/p] denote the Legendre symbol and 1/b denote the inverse of b mod p. Then, for m and n, where n is not divisible by p,

[(m+n)/p] == [n/p]*Sum_{k=0..(p-1)/2} (-m/(4*n))^k * a(k) (mod p).

Evaluating this identity for m = -1 and n = 1 demonstrates that, for all odd primes p, Sum_{k=0..(p-1)/2} (1/4)^k * a(k) is divisible by p. (End)

Number of vertices of the subgraph of the (2n-1)-dimensional hypercube induced by all bitstrings with n-1 or n many 1s. The middle levels conjecture asserts that this graph has a Hamilton cycle. - Torsten Muetze, Feb 11 2019

a(n) is the number of walks of length 2n from the origin with steps (1,1) and (1,-1) that stay on or above the x-axis. Equivalently, a(n) is the number of walks of length 2n from the origin with steps (1,0) and (0,1) that stay in the first octant. - Alexander Burstein, Dec 24 2019

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {3>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second element but smaller than the third elements. - Sergey Kitaev, Dec 08 2020

From Gus Wiseman, Jul 21 2021: (Start)

Also the number of integer compositions of 2n+1 with alternating sum 1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 1 through a(2) = 6 compositions are:

(1) (2,1) (3,2)

(1,1,1) (1,2,2)

(2,2,1)

(1,1,2,1)

(2,1,1,1)

(1,1,1,1,1)

The following relate to these compositions:

- The unordered version is A000070.

- The alternating sum -1 version is counted by A001791, ranked by A345910/A345912.

- The alternating sum 0 version is counted by A088218, ranked by A344619.

- Including even indices gives A126869.

- The complement is counted by A202736.

- Ranked by A345909 (reverse: A345911).

Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 1 than 0's. For example, the a(2) = 6 binary numbers are: 10011, 10101, 10110, 11001, 11010, 11100.

(End)

From Michael Wallner, Jan 25 2022: (Start)

a(n) is the number of nx2 Young tableaux with a single horizontal wall between the first and second column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021].

Example for a(2)=6:

3 4 2 4 3 4 3|4 4|3 2|4

1|2, 1|3, 2|1, 1 2, 1 2, 1 3

a(n) is also the number of nx2 Young tableaux with n "walls" between the first and second column.

Example for a(2)=6:

3|4 2|4 4|3 3|4 4|3 4|2

1|2, 1|3, 1|2, 2|1, 2|1, 3|1 (End)

From Shel Kaphan, Jan 12 2023: (Start)

a(n)/4^n is the probability that a fair coin tossed 2n times will come up heads exactly n times and tails exactly n times, or that a random walk with steps of +-1 will return to the starting point after 2n steps (not necessarily for the first time). As n becomes large, this number asymptotically approaches 1/sqrt(n*Pi), using Stirling's approximation for n!.

a(n)/(4^n*(2n-1)) is the probability that a random walk with steps of +-1 will return to the starting point for the first time after 2n steps. The absolute value of the n-th term of A144704 is denominator of this fraction.

Considering all possible random walks of exactly 2n steps with steps of +-1, a(n)/(2n-1) is the number of such walks that return to the starting point for the first time after 2n steps. See the absolute values of A002420 or A284016 for these numbers. For comparison, as mentioned by Stefan Hollos, Dec 10 2007, a(n) is the number of such walks that return to the starting point after 2n steps, but not necessarily for the first time. (End)

p divides a((p-1)/2) + 1 for primes p of the form 4*k+3 (A002145). - Jules Beauchamp, Feb 11 2023

Also the size of the shuffle product of two words of length n, such that the union of the two words consist of 2n distinct elements. - Robert C. Lyons, Mar 15 2023

a(n) is the number of vertices of the n-dimensional cyclohedron W_{n+1}. - Jose Bastidas, Mar 25 2025

Consider a stack of pancakes of height n, where the only allowed operation is reversing the top portion of the stack. First, perform a series of reversals of increasing sizes, followed by a series of reversals of decreasing sizes. The number of distinct permutations of the initial stack that can be reached through these operations is a(n). - Thomas Baruchel, May 12 2025

Number of 4321-, (3412,2413)-, (3412,3142)- and 3412-avoiding involutions in S_n.

Number of sequences of length n-1 consisting of positive integers such that the first and last elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - Jon Perry, Sep 04 2003

From David Callan, Jul 15 2004: (Start)

Also number of Motzkin n-paths: paths from (0,0) to (n,0) in an n X n grid using only steps U = (1,1), F = (1,0) and D = (1,-1).

Number of Dyck n-paths with no UUU. (Given such a Dyck n-path, change each UUD to U, then change each remaining UD to F. This is a bijection to Motzkin n-paths. Example with n=5: U U D U D U U D D D -> U F U D D.)

Number of Dyck (n+1)-paths with no UDU. (Given such a Dyck (n+1)-path, mark each U that is followed by a D and each D that is not followed by a U. Then change each unmarked U whose matching D is marked to an F. Lastly, delete all the marked steps. This is a bijection to Motzkin n-paths. Example with n=6 and marked steps in small type: U U u d D U U u d d d D u d -> U U u d D F F u d d d D u d -> U U D F F D.) (End)

a(n) is the number of strings of length 2n+2 from the following recursively defined set: L contains the empty string and, for any strings a and b in L, we also find (ab) in L. The first few elements of L are e, (), (()), ((())), (()()), (((()))), ((()())), ((())()), (()(())) and so on. This proves that a(n) is less than or equal to C(n), the n-th Catalan number. See Orrick link (2024). - Saul Schleimer (saulsch(AT)math.rutgers.edu), Feb 23 2006 (Additional linked comment added by William P. Orrick, Jun 13 2024.)

a(n) = number of Dyck n-paths all of whose valleys have even x-coordinate (when path starts at origin). For example, T(4,2)=3 counts UDUDUUDD, UDUUDDUD, UUDDUDUD. Given such a path, split it into n subpaths of length 2 and transform UU->U, DD->D, UD->F (there will be no DUs for that would entail a valley with odd x-coordinate). This is a bijection to Motzkin n-paths. - David Callan, Jun 07 2006

Also the number of standard Young tableaux of height <= 3. - Mike Zabrocki, Mar 24 2007

a(n) is the number of RNA shapes of size 2n+2. RNA Shapes are essentially Dyck words without "directly nested" motifs of the form A[[B]]C, for A, B and C Dyck words. The first RNA Shapes are []; [][]; [][][], [[][]]; [][][][], [][[][]], [[][][]], [[][]][]; ... - Yann Ponty (ponty(AT)lri.fr), May 30 2007

The sequence is self-generated from top row A going to the left starting (1,1) and bottom row = B, the same sequence but starting (0,1) and going to the right. Take dot product of A and B and add the result to n-th term of A to get the (n+1)-th term of A. Example: a(5) = 21 as follows: Take dot product of A = (9, 4, 2, 1, 1) and (0, 1, 1, 2, 4) = (0, + 4 + 2 + 2 + 4) = 12; which is added to 9 = 21. - Gary W. Adamson, Oct 27 2008

Equals A005773 / A005773 shifted (i.e., (1,2,5,13,35,96,...) / (1,1,2,5,13,35,96,...)). - Gary W. Adamson, Dec 21 2008

Starting with offset 1 = iterates of M * [1,1,0,0,0,...], 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 07 2009

a(n) is the number of involutions 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(4)=9; indeed, p=3412=(13)(24) is the only involution of {1,2,3,4} with genus > 0. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference). [Also, redundantly, for p=3412=(13)(24) we have cp'=2341*3412=4123=(1432) and so g(p)=(1/2)(4+1-2-1)=1.] - Emeric Deutsch, May 29 2010

Let w(i,j,n) denote walks in N^2 which satisfy the multivariate recurrence w(i,j,n) = w(i, j + 1, n - 1) + w(i - 1, j, n - 1) + w(i + 1, j - 1, n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Then a(n) = Sum_{i = 0..n, j = 0..n} w(i,j,n) is the number of such walks of length n. - Peter Luschny, May 21 2011

a(n)/a(n-1) tends to 3.0 as N->infinity: (1+2*cos(2*Pi/N)) relating to longest odd N regular polygon diagonals, by way of example, N=7: Using the tridiagonal generator [cf. comment of Jan 07 2009], for polygon N=7, we extract an (N-1)/2 = 3 X 3 matrix, [0,1,0; 1,1,1; 0,1,1] with an e-val of 2.24697...; the longest Heptagon diagonal with edge = 1. As N tends to infinity, the diagonal lengths tend to 3.0, the convergent of the sequence. - Gary W. Adamson, Jun 08 2011

Number of (n+1)-length permutations avoiding the pattern 132 and the dotted pattern 23\dot{1}. - Jean-Luc Baril, Mar 07 2012

Number of n-length words w over alphabet {a,b,c} such that for every prefix z of w we have #(z,a) >= #(z,b) >= #(z,c), where #(z,x) counts the letters x in word z. The a(4) = 9 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca. - Alois P. Heinz, May 26 2012

Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=1, r(k)<=k, and r(k)!=r(k-1); for example, the 9 RGS for n=4 are 1010, 1012, 1201, 1210, 1212, 1230, 1231, 1232, 1234. - Joerg Arndt, Apr 16 2013

Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=0, r(k)<=k and r(k)-r(k-1) != 1; for example, the 9 RGS for n=4 are 0000, 0002, 0003, 0004, 0022, 0024, 0033, 0222, 0224. - Joerg Arndt, Apr 17 2013

Number of (4231,5276143)-avoiding involutions in S_n. - Alexander Burstein, Mar 05 2014

a(n) is the number of increasing unary-binary trees with n nodes that have an associated permutation that avoids 132. For more information about unary-binary trees with associated permutations, see A245888. - Manda Riehl, Aug 07 2014

a(n) is the number of involutions on [n] avoiding the single pattern p, where p is any one of the 8 (classical) patterns 1234, 1243, 1432, 2134, 2143, 3214, 3412, 4321. Also, number of (3412,2413)-, (3412,3142)-, (3412,2413,3142)-avoiding involutions on [n] because each of these 3 sets actually coincides with the 3412-avoiding involutions on [n]. This is a complete list of the 8 singles, 2 pairs, and 1 triple of 4-letter classical patterns whose involution avoiders are counted by the Motzkin numbers. (See Barnabei et al. 2011 reference.) - David Callan, Aug 27 2014

From Tony Foster III, Jul 28 2016: (Start)

A series created using 2*a(n) + a(n+1) has Hankel transform of F(2n), offset 3, F being the Fibonacci bisection, A001906 (empirical observation).

A series created using 2*a(n) + 3*a(n+1) + a(n+2) gives the Hankel transform of Sum_{k=0..n} k*Fibonacci(2*k), offset 3, A197649 (empirical observation). (End)

Conjecture: (2/n)*Sum_{k=1..n} (2k+1)*a(k)^2 is an integer for each positive integer n. - Zhi-Wei Sun, Nov 16 2017

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." - Eric M. Schmidt, Dec 16 2017

Number of U_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - Sergey Kirgizov, Apr 08 2018

If tau_1 and tau_2 are two distinct permutation patterns chosen from the set {132,231,312}, then a(n) is the number of valid hook configurations of permutations of [n+1] that avoid the patterns tau_1 and tau_2. - Colin Defant, Apr 28 2019

Number of permutations of length n that are sorted to the identity by a consecutive-321-avoiding stack followed by a classical-21-avoiding stack. - Colin Defant, Aug 29 2020

From Helmut Prodinger, Dec 13 2020: (Start)

a(n) is the number of paths in the first quadrant starting at (0,0) and consisting of n steps from the infinite set {(1,1), (1,-1), (1,-2), (1,-3), ...}.

For example, denoting U=(1,1), D=(1,-1), D_ j=(1,-j) for j >= 2, a(4) counts UUUU, UUUD, UUUD_2, UUUD_3, UUDU, UUDD, UUD_2U, UDUU, UDUD.

This step set is inspired by {(1,1), (1,-1), (1,-3), (1,-5), ...}, suggested by Emeric Deutsch around 2000.

See Prodinger link that contains a bijection to Motzkin paths. (End)

Named by Donaghey (1977) after the Israeli-American mathematician Theodore Motzkin (1908-1970). In Sloane's "A Handbook of Integer Sequences" (1973) they were called "generalized ballot numbers". - Amiram Eldar, Apr 15 2021

Number of Motzkin n-paths a(n) is split into A107587(n), number of even Motzkin n-paths, and A343386(n), number of odd Motzkin n-paths. The value A107587(n) - A343386(n) can be called the "shadow" of a(n) (see A343773). - Gennady Eremin, May 17 2021

Conjecture: If p is a prime of the form 6m+1 (A002476), then a(p-2) is divisible by p. Currently, no counterexample exists for p < 10^7. Personal communication from Robert Gerbicz: mod such p this is equivalent to A066796 with comment: "Every A066796(n) from A066796((p-1)/2) to A066796(p-1) is divisible by prime p of form 6m+1". - Serge Batalov, Feb 08 2022

From Rob Burns, Nov 11 2024: (Start)

The conjecture is proved in the 2017 paper by Rob Burns in the Links below. The result is contained in Tables 4 and 5 of the paper, which show that a(p-2) == 0 (mod p) when p == 1 (mod 6) and a(p-2) == -1 (mod p) when p == -1 (mod 6).

In fact, the 2017 paper by Burns establishes more general congruences for a(p^k - 2) where k >= 1.

If p == 1 (mod 6) then a(p^k - 2) == 0 (mod p) for k >= 1.

If p == -1 (mod 6) then a(p^k - 2) == -1 (mod p) when k is odd and a(p^k - 2) == 0 (mod p) when k is even.

These are consequences of the transitions provided in Tables 4, 5 and 6 of the paper.

The 2024 paper by Nadav Kohen also proves the conjecture. Proposition 6 of the paper states that a prime p divides a(p-2) if and only if p = (1 mod 3). (End)

From Peter Bala, Feb 10 2022: (Start)

Conjectures:

(1) For prime p == 1 (mod 6) and n, r >= 1, a(n*p^r - 2) == -A005717(n-1) (mod p), where we take A005717(0) = 0 to match Batalov's conjecture above.

(2) For prime p == 5 (mod 6) and n >= 1, a(n*p - 2) == -A005773(n) (mod p).

(3) For prime p >= 3 and k >= 1, a(n + p^k) == a(n) (mod p) for 0 <= n <= (p^k - 3).

(4) For prime p >= 5 and k >= 2, a(n + p^k) == a(n) (mod p^2) for 0 <= n <= (p^(k-1) - 3). (End)

The Hankel transform of this sequence with a(0) omitted gives the period-6 sequence [1, 0, -1, -1, 0, 1, ...] which is A010892 with its first term omitted, while the Hankel transform of the current sequence is the all-ones sequence A000012, and also it is the unique sequence with this property which is similar to the unique Hankel transform property of the Catalan numbers. - Michael Somos, Apr 17 2022

The number of terms in which the exponent of any variable x_i is not greater than 2 in the expansion of Product_{j=1..n} Sum_{i=1..j} x_i. E.g.: a(4) = 9: 3*x1^2*x2^2, 4*x1^2*x2*x3, 2*x1^2*x2*x4, x1^2*x3^2, x1^2*x3*x4, 2*x1*x2^2*x3, x1*x2^2*x4, x1*x2*x3^2, x1*x2*x3*x4. - Elif Baser, Dec 20 2024

3 does not divide binomial(2s, s) if and only if s is a member of this sequence, where binomial(2s, s) = A000984(s) are the central binomial coefficients.

This is the lexicographically earliest increasing sequence of nonnegative numbers that contains no arithmetic progression of length 3. - Robert Craigen (craigenr(AT)cc.umanitoba.ca), Jan 29 2001

In the notation of A185256 this is the Stanley Sequence S(0,1). - N. J. A. Sloane, Mar 19 2010

Complement of A074940. - Reinhard Zumkeller, Mar 23 2003

Sums of distinct powers of 3. - Ralf Stephan, Apr 27 2003

Numbers n such that central trinomial coefficient A002426(n) == 1 (mod 3). - Emeric Deutsch and Bruce E. Sagan, Dec 04 2003

A039966(a(n)+1) = 1; A104406(n) = number of terms <= n.

Subsequence of A125292; A125291(a(n)) = 1 for n>1. - Reinhard Zumkeller, Nov 26 2006

Also final value of n - 1 written in base 2 and then read in base 3 and with finally the result translated in base 10. - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007

a(n) modulo 2 is the Thue-Morse sequence A010060. - Dennis Tseng, Jul 16 2009

Also numbers such that the balanced ternary representation is the same as the base 3 representation. - Alonso del Arte, Feb 25 2011

Fixed point of the morphism: 0 -> 01; 1 -> 34; 2 -> 67; ...; n -> (3n)(3n+1), starting from a(1) = 0. - Philippe Deléham, Oct 22 2011

It appears that this sequence lists the values of n which satisfy the condition sum(binomial(n, k)^(2*j), k = 0..n) mod 3 <> 0, for any j, with offset 0. See Maple code. - Gary Detlefs, Nov 28 2011

Also, it follows from the above comment by Philippe Lallouet that the sequence must be generated by the rules: a(1) = 0, and if m is in the sequence then so are 3*m and 3*m + 1. - L. Edson Jeffery, Nov 20 2015

Add 1 to each term and we get A003278. - N. J. A. Sloane, Dec 01 2019

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

When the rows are centered about their midpoints, each term is the sum of the three terms directly above it (assuming the undefined terms in the previous row are zeros). - N. J. A. Sloane, Dec 23 2021

T(n,k) = number of integer strings s(0),...,s(n) such that s(0)=0, s(n)=k, s(i) = s(i-1) + c, where c is 0, 1 or 2. Columns of T include A002426, A005717 and A014531.

Also number of ordered trees having n+1 leaves, all at level three and n+k+3 edges. Example: T(3,5)=3 because we have three ordered trees with 4 leaves, all at level three and 11 edges: the root r has three children; from one of these children two paths of length two are hanging (i.e., 3 possibilities) while from each of the other two children one path of length two is hanging. Diagonal sums are the tribonacci numbers; more precisely: Sum_{i=0..floor(2*n/3)} T(n-i,i) = A000073(n+2). - Emeric Deutsch, Jan 03 2004

T(n,k) = A111808(n,k) for 0 <= k <= n and T(n, 2*n-k) = A111808(n,k) for 0 <= k < n. - Reinhard Zumkeller, Aug 17 2005

The trinomial coefficients, T(n,i), are the absolute value of the coefficients of the chromatic polynomial of P_2 X P_n factored with x*(x-1)^i terms. Example: The chromatic polynomial of P_2 X P_2 is: x*(x-1) - 2*x*(x-1)^2 + x*(x-1)^3 and so T(1,0)=1, T(1,1)=2 and T(1,1) = 1. - Thomas J. Pfaff (tpfaff(AT)ithaca.edu), Oct 02 2006

T(n,k) is the number of distinct ways in which k unlabeled objects can be distributed in n labeled urns allowing at most 2 objects to fall into each urn. - N-E. Fahssi, Mar 16 2008

T(n,k) is the number of compositions of k into n parts p, each part 0 <= p <= 2. Adding 1 to each part, as a corollary, T(n,k) is the number of compositions of n+k into n parts p where 1 <= p <= 3. E.g., T(2,3)=2 since 5 = 3+2 = 2+3. - Steffen Eger, Jun 10 2011

Number of lattice paths from (0,0) to (n,k) using steps (1,0), (1,1), (1,2). - Joerg Arndt, Jul 05 2011

Number of lattice paths from (0,0) to (2*n-k,k) using steps (2,0), (1,1), (0,2). - Werner Schulte, Jan 25 2017

T(n,k) is number of distinct ways to sum the integers -1, 0 , and 1 n times to obtain n-k, where T(n,0) = T(n,2*n+1) = 1. - William Boyles, Apr 23 2017

T(n-1,k-1) is the number of 2-compositions of n with 0's having k parts; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020

T(n,k) is the number of ways to obtain a sum of n+k when throwing a 3-sided die n times. Follows from the "T(n,k) is the number of compositions of n+k into n parts p where 1 <= p <= 3" comment above. - Feryal Alayont, Dec 30 2024

This sequence, with first term a(0) deleted, appears to be determined by the conditions that the diagonal and first superdiagonal of U are {1,1,1,1,...} and {2,3,4,5,...,n+1,...} respectively, where A=LU is the LU factorization of the Hankel matrix A given by [{a(1),a(2),...}, {a(2),a(3),...}, ..., {a(n),a(n+1),...}, ...]. - John W. Layman, Jul 21 2000

Also the number of base 3 n-digit numbers (not starting with 0) with digit sum n. For the analogous sequence in base 10 see A071976, see example. - John W. Layman, Jun 22 2002

Also number of paths in an n X n grid from (0,0) to the line x=n-1, using only steps U=(1,1), H=(1,0) and D=(1,-1) (i.e., left factors of length n-1 of Motzkin paths, palindromic Motzkin paths of length 2n-2 or 2n-1). Example: a(3)=5, namely, HH, UD, HU, UH and UU. Also number of ordered trees with n edges and having nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 01 2002

Number of symmetric Dyck paths of semilength 2n-1 with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUD, UDUUUDDDUD, UUUUUDDDDD, UUUDUDUDDD and UUUDDUUDDD, where U=(1,1) and D=(1,-1). Also number of symmetric Dyck paths of semilength 2n with no peaks at even level. Example: a(3)=5 because we have UDUDUDUDUDUD, UDUUUDUDDDUD, UUUDUDUDUDDD, UUUUUDUDDDDD and UUUDDDUUUDDD. - Emeric Deutsch, Nov 21 2003

a(n) is the sum of the (n-1)-st central trinomial coefficient and its predecessor. Example: a(4) = 6 + 7 and (1 + x + x^2)^3 = ... + 6*x^2 + 7*x^3 + ... . - David Callan, Feb 07 2004

a(n) is the number of UDU-free paths of n upsteps (U) and n downsteps (D) that start U (n>=1). Example: a(2)=2 counts UUDD, UDDU. - David Callan, Aug 18 2004

a(n) is also the number of Grand-Dyck paths of semilength n starting with an up-step and avoiding the pattern DUD. - David Bevan, Nov 19 2019

Hankel transform of a(n+1) = [1,2,5,13,35,96,...] gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

Equals row sums of triangle A136787 starting (1, 2, 5, 13, 35, ...). - Gary W. Adamson, Jan 21 2008

a(n) is the number of permutations on [n] that avoid the patterns 1-23-4 and 1-3-2, where the omission of a dash in a pattern means the permutation entries must be adjacent. Example: a(4) = 13 counts all 14 (Catalan number) (1-3-2)-avoiding permutations on [4] except 1234. - David Callan, Jul 22 2008

a(n) is also the number of involutions of length 2n-2 which are invariant under the reverse-complement map and have no decreasing subsequences of length 4. - Eric S. Egge, Oct 21 2008

Hankel transform is A010892. - Paul Barry, Jan 19 2009

a(n) is the number of Dyck words of semilength n with no DUUU. For example, a(4) = 14-1 = 13 because there is only one Dyck 4-word containing DUUU, namely UDUUUDDD. - Eric Rowland, Apr 21 2009

Inverse binomial transform of A024718. - Philippe Deléham, Dec 13 2009

Let w(i, j, n) denote walks in N^2 which satisfy the multivariate recurrence

w(i, j, n) = w(i - 1, j, n - 1) + w(i, j - 1, n - 1) + w(i + 1, j - 1,n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Let alpha(n) the number of such walks of length n, alpha(n) = Sum_{i = 0..n, j=0..n} w(i, j, n). Then a(n+1) = alpha(n). - Peter Luschny, May 21 2011

Number of length-n strings [d(0),d(1),d(2),...,d(n-1)] where 0 <= d(k) <= k and abs(d(k) - d(k-1)) <= 1 (smooth factorial numbers, see example). - Joerg Arndt, Nov 10 2012

a(n) is the number of n-multisets of {1,...,n} containing no pair of consecutive integers (e.g., 111, 113, 133, 222, 333 for n=3). - David Bevan, Jun 10 2013

a(n) is also the number of n-multisets of [n] in which no integer except n occurs exactly once (e.g., 111, 113, 222, 223, 333 for n=3). - David Bevan, Nov 19 2019

Number of minimax elements in the affine Weyl group of the Lie algebra so(2n+1) or the Lie algebra sp(2n). See Panyushev 2005. Cf. A245455. - Peter Bala, Jul 22 2014

The shifted, signed array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating (here t=-2) o.g.f. G(x,t) = (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse o.g.f. Ginv(x,t) = x(1-x)/(1+(t-1)x(1-x)) (A057682). See A091867 for more info on this family. - Tom Copeland, Nov 09 2014

Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at any altitude, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016

Let N be a squarefree number with n prime factors: p_1 < p_2 < ... < p_n. Let D be its set of divisors, E the subset of D X D made of the (d_1, d_2) for which, provided that we know which p_i are in d_1, which p_i are in d_2, d_1 <= d_2 is provable without needing to know the numerical values of the p_i. It appears that a(n+1) is the number of (d_1, d_2) in E such that d_1 and d_2 are coprime. - Luc Rousseau, Aug 21 2017

Number of ordered rooted trees with n non-root nodes and all non-root nodes having outdegrees 1 or 2. - Andrew Howroyd, Dec 04 2017

a(n) is the number of compositions (ordered partitions) of n where there are A001006(k-1) sorts of part k (see formula by Andrew Howroyd, Dec 04 2017). - Joerg Arndt, Jan 26 2024

Number of walks of length n between any two distinct vertices of the complete graph K_4. - Paul Barry and Emeric Deutsch, Apr 01 2004

For n >= 1, a(n) is the number of integers k, 1 <= k <= 3^(n-1), whose ternary representation ends in an even number of zeros (see A007417). - Philippe Deléham, Mar 31 2004

Form the digraph with matrix A=[0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. A015518(n) corresponds to the (1,3) term of A^n. - Paul Barry, Oct 02 2004

The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005

(A046717(n))^2 + (2*a(n))^2 = A046717(2n). E.g., A046717(3) = 13, 2*a(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006

For n >= 2, number of ordered partitions of n-1 into parts of sizes 1 and 2 where there are two types of 1 (singletons) and three types of 2 (twins). For example, the number of possible configurations of families of n-1 male (M) and female (F) offspring considering only single births and twins, where the birth order of M/F/pair-of-twins is considered and there are three types of twins; namely, both F, both M, or one F and one M - where birth order within a pair of twins itself is disregarded. In particular, for a(3)=7, two children could be either: (1) F, then M; (2) M, then F; (3) F,F; (4) M,M; (5) F,F twins; (6) M,M twins; or (7) M,F twins (emphasizing that birth order is irrelevant here when both/all children are the same gender and when two children are within the same pair of twins). - Rick L. Shepherd, Sep 18 2004

a(n) is prime for n = {2, 3, 5, 7, 13, 23, 43, 281, 359, ...}, where only a(2) = 2 corresponds to a prime of the form (3^k - 1)/4. All prime terms, except a(2) = 2, are the primes of the form (3^k + 1)/4. Numbers k such that (3^k + 1)/4 is prime are listed in A007658. Note that all prime terms have prime indices. Prime terms are listed in A111010. - Alexander Adamchuk, Nov 19 2006

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 26 2010

Select an odd size subset S from {1,2,...,n}, then select an even size subset from S. - Geoffrey Critzer, Mar 02 2010

a(n) is the number of ternary sequences of length n where the numbers of (0's, 1's) are (even, odd) respectively, and, by symmetry, the number of such sequences where those numbers are (odd, even) respectively. A122983 covers (even, even), and A081251 covers (odd, odd). - Toby Gottfried, Apr 18 2010

An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 341, leads to this sequence (without the leading 0). For the central square this vector leads to the companion sequence A046717 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010

Let R be the commutative algebra resulting from adjoining the elements of the Klein four-group to the integers (equivalently, K = Z[x,y,z]/{x*y - z, y*z - x, x*z - y, x^2 - 1, y^2 - 1, z^2 - 1}). Then a(n) is equal to the coefficients of x, y, and z in the expansion of (x + y + z)^n. - Joseph E. Cooper III (easonrevant(AT)gmail.com), Nov 06 2010

Pisano period lengths: 1, 2, 2, 4, 4, 2, 6, 8, 2, 4, 10, 4, 6, 6, 4, 16, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012

The ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - Felix P. Muga II, Mar 09 2014

This is a divisibility sequence, also the values of Chebyshev polynomials, and also the number of ways of packing a 2 X n-1 rectangle with dominoes and unit squares. - R. K. Guy, Dec 16 2016

For n>0, gcd(a(n),a(n+1))=1. - Kengbo Lu, Jul 02 2020

The expression a(n) = B^n*Sum_{ k=0..n } binomial(2*k,k)/B^k gives A006134 for B=1, A082590 (B=2), A132310 (B=3), A002457 (B=4), A144635 (B=5). - N. J. A. Sloane, Jan 21 2009

T(n+1,1) from table A045912 of characteristic polynomial of negative Pascal matrix. - Michael Somos, Jul 24 2002

p divides a((p-3)/2) for p=11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, ...: A097933. Also primes congruent to {1, 2, 3, 11} mod 12 or primes p such that 3 is a square mod p (excluding 2 and 3) A038874. - Alexander Adamchuk, Jul 05 2006

Partial sums of the even central binomial coefficients. For p prime >=5, a(p-1) = 1 or -1 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). - David Callan, Nov 29 2007

First column of triangle A187887. - Michel Marcus, Jun 23 2013

From Gus Wiseman, Apr 20 2023: (Start)

Also the number of nonempty subsets of {1,...,2n+1} with median n+1, where the median of a multiset is either the middle part (for odd length), or the average of the two middle parts (for even length). The odd/even-length cases are A000984 and A006134(n-1). For example, the a(0) = 1 through a(2) = 9 subsets are:

{1} {2} {3}

{1,3} {1,5}

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

{1,3,4}

{1,3,5}

{2,3,4}

{2,3,5}

{1,2,4,5}

{1,2,3,4,5}

Alternatively, a(n-1) is the number of nonempty subsets of {1,...,2n-1} with median n.

(End)