0,3

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 (deutsch(AT)duke.poly.edu), 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 (callan(AT)stat.wisc.edu), 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 (pbarry(AT)wit.ie), 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 (callan(AT)stat.wisc.edu), 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,-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 (callan(AT)stat.wisc.edu), Jul 22 2008

Central terms of pendular triangle A167763. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 12 2009]

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

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

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

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

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

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.

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.

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

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

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

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347. See also the P\'olya-Szeg\"o reference.

G. P\'olya and G. Szeg\"o, 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.

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

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

Joerg Arndt, Fxtbook

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.

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

M. Bousquet-M\'elou and M. Petkov\v{s}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

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

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

H. Niederhausen, Catalan Traffic at the Beach.

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.

M. Somos, Number Walls in Combinatorics.

Index entries for "core" sequences

Index entries for sequences related to trees

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

G.f.: 2/sqrt(3x)sin(1/3 arcsin(sqrt(27x/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. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Nov 08 2001

G.f. A(x) satisfies A(x) = 1+xA(x)^3 = 1/(1-xA(x)^2) - Ralf Stephan (ralf(AT)ark.in-berlin.de), 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).

a(n)=binomial(3*n,n-1)/n, n>=1, a(0)=1. From the Lagrange series of the o.g.f. A(x) with its above given implicit equation.

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.

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 (zerinvarylajos(AT)yahoo.com), 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 (zerinvarylajos(AT)yahoo.com), Apr 25 2008

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

(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))) [From Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Oct 08 2008]

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

A column of triangle A102537.

Bisection of A047749 and A047761.

Row sums of triangle A108410.

Second column of triangle A062993.

Sequence in context: A042971 A024038 A007199 this_sequence A120920 A064314 A107318

Adjacent sequences: A001761 A001762 A001763 this_sequence A001765 A001766 A001767

easy,nonn,nice,core,new

N. J. A. Sloane (njas(AT)research.att.com).