login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001764 Binomial(3n,n)/(2n+1) (enumerates ternary trees and also noncrossing trees).
(Formerly M2926 N1174)
266
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)
OFFSET

0,3

COMMENTS

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. 2sqrt(3)sin(arcsin(3sqrt(3)x/2)/3)/(3x) 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 Down-steps=(1,k); where k<= -1 and stays above the x-axis. For example, a(2)= 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)] Also 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 soln. of the inviscid Burgers', or Hopf, eqn. 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 characterics for the Hopf eqn. 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

REFERENCES

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, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

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.

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

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

J. Cigler, Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results, http://homepage.univie.ac.at/Johann.Cigler/preprints/chebyshev-survey.pdf, 2013.

S. J. Cyvin et al., Enumeration of staggered conformers of alkanes: complete solution ..., J. Molec. Struct., 413 (1997), 237-239.

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

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.

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, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.

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.

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

Kuba, Markus; Panholzer, Alois. 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. 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.

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

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

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

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.

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

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

Anssi Yli-Jyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158; http://rd.springer.com/chapter/10.1007%2F978-3-642-30773-7_10?LI=true. - From N. J. A. Sloane, Dec 25 2012

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; http://dx.doi.org/10.1155/2014/848374

LINKS

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

O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13-th 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 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)

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

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

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

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

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. - From N. J. A. Sloane, Dec 31 2012

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

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

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.

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

Index entries for "core" sequences

Index entries for sequences related to trees

FORMULA

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

EXAMPLE

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

MAPLE

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

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

MATHEMATICA

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

PROG

(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

(Sage)

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

CROSSREFS

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.

Sequence in context: A024038 A007199 A179848 * A171780 A216493 A216494

Adjacent sequences:  A001761 A001762 A001763 * A001765 A001766 A001767

KEYWORD

easy,nonn,nice,core

AUTHOR

N. J. A. Sloane

STATUS

approved

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 31 07:49 EDT 2014. Contains 248845 sequences.