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


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

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

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

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

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

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

I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.

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.

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

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

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

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

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

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).


T. D. Noe, Table of n, a(n) for n=0..100

A. Aggarwal, Armstrong's Conjecture for (k, mk+1)-Core Partitions, arXiv preprint arXiv:1407.5134, 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.

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

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

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

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.

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

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.

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

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

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

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.

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

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

I. Gessel and G. Xin, The generating function of ternary trees and continued fractions

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

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

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.

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, 2012.

Don Knuth, 20th Anniversary Christmas Tree Lecture

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 formulae 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.

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, 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, 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.

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, 2014

M. Somos, Number Walls in Combinatorics.

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

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


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.

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) = local(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.

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 5 20:04 EDT 2015. Contains 262317 sequences.