This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001764 a(n) = binomial(3n,n)/(2n+1) (enumerates ternary trees and also noncrossing trees).
(Formerly M2926 N1174)
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, 8414640, 50067108, 300830572, 1822766520, 11124755664, 68328754959, 422030545335, 2619631042665, 16332922290300, 102240109897695, 642312451217745, 4048514844039120, 25594403741131680, 162250238001816900 (list; graph; refs; listen; history; text; internal format)



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

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

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

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

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

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

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

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

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

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

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

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

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

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

a(n) = A258708(2*n,n) for n > 0. - Reinhard Zumkeller, Jun 23 2015

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

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


I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.

I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347. See also the Pólya-Szegő reference.

W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.

T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.

G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).


G. C. Greubel, Table of n, a(n) for n = 0..1000[Terms 0 to 100 computed by T. D. Noe; Terms 101 to 1000 by G. C. Greubel, Jan 13 2017]

A. Aggarwal, Armstrong's Conjecture for (k, mk+1)-Core Partitions, arXiv preprint arXiv:1407.5134 [math.CO], 2014.

O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.

M. H. Albert, R. E. L. Allred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, D. A. Holton, Restricted permutations and queue jumping, Discrete Math. 287 (2004), 129-133.

N. Alexeev, A. Tikhomirov, Singular Values Distribution of Squares of Elliptic Random Matrices and type-B Narayana Polynomials, arXiv preprint arXiv:1501.04615 [math.PR], 2015.

Joerg Arndt, Matters Computational (The Fxtbook), pp. 337-338

J. Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.

Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.

I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.

Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 87-98.

L. W. Beineke and R. E. Pippert, Enumerating dissectable polyhedra by their automorphism groups, Canad. J. Math., 26 (1974), 50-67.

Francois Bergeron, Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices, arXiv:1202.6269 [math.CO], (3-March-2012)

Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, Journal of Combinatorial Theory, Series A 116:1 (2009), pp. 55-75. See also Bernardi's slides, Catalan lattices and realizers of triangulations (April 2007).

D. Bevan, D. Levin, P. Nugent, J. Pantone, L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510:08036 [math.CO], 2015.

D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.

M. Bousquet-Mélou and M. Petkovšek, Walks confined in a quadrant are not always D-finite, arXiv:math/0211432 [math.CO], 2002.

N. T. Cameron, Random walks, trees and extensions of Riordan group techniques

Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, arXiv:math/0504342 [math.CO], 2005.

J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, arXiv:1312.2767 [math.CO], 2013.

T. C. Copeland, Compositional inverse pairs, the Burgers-Hopf equation, and the Stasheff associahedra,

T. C. Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers

S. J. Cyvin et al., Staggered conformers of alkanes: complete solution of the enumeration problem, J. Molec. Struct., 413 (1997), 227-239.

S. J. Cyvin et al., Enumeration of staggered conformers of alkanes and monocyclic cycloalkanes, J. Molec. Struct., 445 (1998), 127-13.

E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645-654.

S. Dulucq, Etude combinatorie de problemes d'enumeration, d'algorithmique sure les arbres et de codage par des mots, a thesis presented to L'Universite De Bordeaux I, 1987. (Annotated scanned copy)

E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75-87.

R. Dickau, Fuss-Catalan Numbers. Figures of various interpretations.

C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.

C. Domb & A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358. (Annotated scanned copy)

C. Domb & A. J. Barrett, Notes on Table 2 in "Enumeration of ladder graphs", Discrete Math. 9 (1974), 55. (Annotated scanned copy)

J. A. Eidswick, Short factorizations of permutations into transpositions, Disc. Math. 73 (1989) 239-243

I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.

I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.

I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486

N. Gabriel, K. Peske, L. Pudwell, S. Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012) # 12.1.5

I. Gessel and G. Xin, The generating function of ternary trees and continued fractions, arXiv:math/0505217 [math.CO], 2005.

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

T.-X. He, L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41, Fuss-Catalan Number (F_3)_n

V. E. Hoggatt, Jr., Letters to N. J. A. Sloane, 1974-1975

V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.

V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.

Vera M. Hur, M. A. Johnson, J. L. Martin, Oscillation estimates of eigenfunctions via the combinatorics of noncrossing partitions, arXiv preprint arXiv:1609.02189 [math.SP], 2016.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 53

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 285

S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on beta(1, 0)-trees, arXiv preprint arXiv:1210.2618 [math.CO], 2012.

Don Knuth, 20th Anniversary Christmas Tree Lecture

G. Kreweras, Sur les partitions non croisées d'un cycle, (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852).

D. V. Kruchinin, On solving some functional equations, Advances in Difference Equations (2015) 2015:17; DOI 10.1186/s13662-014-0347-9.

Dmitry V. Kruchinin and Vladimir V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.6.

Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From N. J. A. Sloane, Sep 25 2012

W. Lang, Ternary trees with n=1,2,3 and 4 vertices.

R. P. Loh, A. G. Shannon, A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.

Lun Lv and Sabrina X.M. Pang, Reduced Decompositions of Matchings, Electronic Journal of Combinatorics 18 (2011), #P107.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344, (T_n for s=3).

W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2-plane trees, arXiv preprint arXiv:1304.6544 [math.PR], 2013.

H. Niederhausen, Catalan Traffic at the Beach.

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195.

K. A. Penson and A. I. Solomon, Coherent states from combinatorial sequences, arXiv:quant-ph/0111151, 2001.

Jocelyn Quaintance, Combinatoric Enumeration of Two-Dimensional Proper Arrays, Discrete Math., 307 (2007), 1844-1864.

B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv preprint arXiv:1401.7194 [math.CO], 2014.

M. Somos, Number Walls in Combinatorics.

B Sury, Generalized Catalan numbers: linear recursion and divisibility, JIS 12 (2009) 09.7.5

S. Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv preprint arXiv:1310.2979 [math.CO], 2013.

Sheng-Liang Yang, LJ Wang, Taylor expansions for the m-Catalan numbers, Australasian Journal of Combinatorics, Volume 64(3) (2016), Pages 420-431.

Anssi Yli-Jyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158;

S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages

Index entries for "core" sequences

Index entries for sequences related to trees


From Karol A. Penson, Nov 08 2001: (Start)

G.f.: (2/sqrt(3*x))*sin((1/3)*arcsin(sqrt(27*x/4))).

E.g.f.: hypergeom([1/3, 2/3], [1, 3/2], 27/4*x).

Integral representation as n-th moment of a positive function on [0, 27/4]: a(n)=int(x^n*(1/12*3^(1/2)*2^(1/3)*(2^(1/3)*(27+3*sqrt(81-12*x))^(2/3)-6*x^(1/3))/Pi/x^(2/3)/(27+3*sqrt(81-12*x))^(1/3)), x=0..6.75), n=0, 1... This representation is unique. (End)

G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2). - Ralf Stephan, Jun 30 2003

a(n) = n-th coefficient in expansion of power series P(n), where P(0)=1, P(k+1) = 1/(1-x*P(k)^2).

G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of). - Paul Barry, Mar 26 2010

From Gary W. Adamson, Jul 07 2011: (Start)

Let M = the production matrix:

1, 1

2, 2, 1

3, 3, 2, 1

4, 4, 3, 2, 1

5, 5, 4, 3, 2, 1


a(n) = upper left term in M^n. Top row terms of M^n = (n+1)-th row of triangle A143603, with top row sums generating A006013: (1, 2, 7, 30, 143, 728,...). (End)

Recurrence: a(0)=1; a(n) = Sum[a(i)a(j)a(n-1-i-j), i=0..n-1, j=0..n-1-i] for n>=1 (counts ternary trees by subtrees of the root). - David Callan, Nov 21 2011

G.f.: 1+6*x/(Q(0)-6*x); Q(k)=3*x*(3*k+1)*(3*k+2)+2*(2*(k^2)+5*k+3)-6*x*(2*(k^2)+5*k+3)*(3*k+4)*(3*k+5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2011

2*n*(2n+1)*a(n)-3*(3n-1)*(3n-2)*a(n-1)=0. - R. J. Mathar, Dec 14 2011

REVERT transform of A115140. BINOMIAL transform is A188687. SUMADJ transform of A188678. HANKEL transform is A051255. INVERT transform of A023053. INVERT transform is A098746. - Michael Somos, Apr 07 2012

(n + 1) * a(n) = A174687(n).

G.f.: F([2/3,4/3], [3/2], 27/4*x) / F([2/3,1/3], [1/2], 27/4*x) where F() is the hypergeometric function. - Joerg Arndt, Sep 01 2012

a(n) = binomial(3*n+1, n)/(3*n+1) = A062993(n+1,1). - Robert FERREOL, Apr 03 2015

0 = a(n)*(-3188646*a(n+2) +20312856*a(n+3) -11379609*a(n+4) +1437501*a(n+5)) + a(n+1)*(+177147*a(n+2) -2247831*a(n+3) +1638648*a(n+4) -238604*a(n+5)) + a(n+2)*(+243*a(n+2) +31497*a(n+3) -43732*a(n+4) +8288*a(n+5)) for all integer n. - Michael Somos, Jun 03 2016

a(n) ~ 3^(3*n+1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). - Ilya Gutkovskiy, Nov 21 2016


a(2)=3 because the only dissections with 5 edges are given by a square dissected by any of the two diagonals and the pentagon with no dissecting diagonal.

G.f. = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...


A001764 := n->binomial(3*n, n)/(2*n+1): seq(A001764(n), n=0..25);

with(combstruct): BB:=[T, {T=Prod(Z, F), F=Sequence(B), B=Prod(F, Z, F)}, unlabeled]:seq(count(BB, size=i), i=0..22); # Zerinvary Lajos, Apr 22 2007

with(combstruct):BB:=[S, {B = Prod(S, S, Z), S = Sequence(B)}, labelled]: seq(count(BB, size=n)/n!, n=0..21); # Zerinvary Lajos, Apr 25 2008

n:=30:G:=series(RootOf(g = 1+x*g^3, g), x=0, n+1):seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 03 2015


InverseSeries[Series[y-y^3, {y, 0, 24}], x] (* then a(n)=y(2n+1)=ways to place non-crossing diagonals in convex (2n+4)-gon so as to create only quadrilateral tiles *) (* Len Smiley, Apr 08 2000 *)

Table[Binomial[3n, n]/(2n+1), {n, 0, 25}] (* Harvey P. Dale, Jul 24 2011 *)


(PARI) {a(n) = if( n<0, 0, (3*n)! / n! / (2*n + 1)!)};

(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x - x^3 + O(x^(2*n + 2))), 2*n + 1))};

(PARI) {a(n) = my(A); if( n<0, 0, A = 1 + O(x); for( m=1, n, A = 1 + x * A^3); polcoeff(A, n))};

(PARI) b=vector(22); b[1]=1; for(n=2, 22, for(i=1, n-1, for(j=1, n-1, for(k=1, n-1, if((i-1)+(j-1)+(k-1)-(n-2), NULL, b[n]=b[n]+b[i]*b[j]*b[k]))))); a(n)=b[n+1]; print1(a(0)); for(n=1, 21, print1(", ", a(n))) \\ Gerald McGarvey, Oct 08 2008

(PARI) Vec(1 + serreverse(Ser(x / (1+x)^3 + O(x^30)))) \\ Gheorghe Coserea, Aug 05 2015


def A001764_list(n) :

    D = [0]*(n+1); D[1] = 1

    R = []; b = false; h = 1

    for i in range(2*n) :

        for k in (1..h) : D[k] += D[k-1]

        if not b : R.append(D[h])

        else : h += 1

        b = not b

    return R

A001764_list(22) # Peter Luschny, May 03 2012

(MAGMA) [Binomial(3*n, n)/(2*n+1): n in [0..30]]; // Vincenzo Librandi, Sep 04 2014


a001764 n = a001764_list !! n

a001764_list = 1 : [a258708 (2 * n) n | n <- [1..]]

-- Reinhard Zumkeller, Jun 23 2015


Cf. A001762, A001763, A064017, A063548, A072247, A072248.

Cf. A143603, A006013.

A column of triangle A102537.

Bisection of A047749 and A047761.

Row sums of triangle A108410.

Second column of triangle A062993.

Cf. A258708, A256311.

Sequence in context: A024038 A007199 A179848 * A171780 A216493 A216494

Adjacent sequences:  A001761 A001762 A001763 * A001765 A001766 A001767




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 22 03:43 EDT 2017. Contains 293756 sequences.