This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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

%I M2926 N1174

%S 1,1,3,12,55,273,1428,7752,43263,246675,1430715,8414640,50067108,

%T 300830572,1822766520,11124755664,68328754959,422030545335,

%U 2619631042665,16332922290300,102240109897695,642312451217745,4048514844039120,25594403741131680,162250238001816900

%N a(n) = binomial(3n,n)/(2n+1) (enumerates ternary trees and also noncrossing trees).

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

%C 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

%C 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

%C 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

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

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

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

%C 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

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

%C Also 3-Raney sequence, see the Graham et al. reference, p. 346-7.

%C 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

%C 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

%C Central terms of pendular triangle A167763. - _Philippe Deléham_, Nov 12 2009

%C With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} 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's, 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

%C a(n) = A258708(2*n,n) for n > 0. - _Reinhard Zumkeller_, Jun 23 2015

%C 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 & Bonichon (2009) and Kreweras (1972) references. - _Noam Zeilberger_, Jun 01 2016

%C Number of sum-indecomposable (4231,42513)-avoiding permutations. Conjecturally, number of sum-indecomposable (2431,45231)-avoiding permutations. - _Alexander Burstein_, Oct 19 2017

%C a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link. - _Caleb Ji_, May 14 2018

%C Number of complete quadrillages of 2n+2-gons. See Baryshnikov p. 12. See also Nov. 10 2014 comments in A134264. - _Tom Copeland_, Jun 04 2018

%C a(n) is the number of 2-regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2-regular tortoise-sortable words on the alphabet [n] (see the Defant and Kravitz link). - _Colin Defant_, Sep 26 2018

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.

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

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

%D 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 W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.

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

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

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

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

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

%H G. C. Greubel, <a href="/A001764/b001764.txt">Table of n, a(n) for n = 0..1000</a> [Terms 0 to 100 computed by T. D. Noe; Terms 101 to 1000 by G. C. Greubel, Jan 13 2017]

%H V. E. Adler, A. B. Shabat, <a href="https://arxiv.org/abs/1810.13198">Volterra chain and Catalan numbers</a>, arXiv:1810.13198 [nlin.SI], 2018.

%H A. Aggarwal, <a href="http://arxiv.org/abs/1407.5134">Armstrong's Conjecture for (k, mk+1)-Core Partitions</a>, arXiv preprint arXiv:1407.5134 [math.CO], 2014.

%H O. Aichholzer and H. Krasser, <a href="http://www.ist.tugraz.at/publications/oaich/psfiles/ak-psotd-01.ps.gz">The point set order type data base: a collection of applications and results</a>, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.

%H M. H. Albert, R. E. L. Allred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, D. A. Holton, <a href="https://doi.org/10.1016/j.disc.2004.08.003">Restricted permutations and queue jumping</a>, Discrete Math. 287 (2004), 129-133.

%H N. Alexeev, A. Tikhomirov, <a href="http://arxiv.org/abs/1501.04615">Singular Values Distribution of Squares of Elliptic Random Matrices and type-B Narayana Polynomials</a>, arXiv preprint arXiv:1501.04615 [math.PR], 2015.

%H M. Almeida, N. Moreira, R. Reis, <a href="http://dx.doi.org/10.1016/j.tcs.2007.07.029">Enumeration and generation with a string automata representation</a>, Theor. Comp. Sci. 387 (2007) 93-102, Theor. 6

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 337-338

%H J. Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014.

%H Jean-Christophe Aval, <a href="http://arxiv.org/abs/0711.0906">Multivariate Fuss-Catalan numbers</a>, arXiv:0711.0906 [math.CO], 2007.

%H Jean-Christophe Aval, <a href="https://doi.org/10.1016/j.disc.2007.08.100">Multivariate Fuss-Catalan numbers</a>, Discrete Math., 308 (2008), 4660-4669.

%H I. Bajunaid et al., <a href="http://www.jstor.org/stable/30037599">Function series, Catalan numbers and random walks on trees</a>, Amer. Math. Monthly 112 (2005), 765-785.

%H Christian Ballot, <a href="https://www.emis.de/journals/JIS/VOL21/Ballot/ballot30.html">Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions</a>, J. Int. Seq., Vol. 21 (2018), Article 18.6.5.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating functions for generating trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H C. Banderier and D. Merlini, <a href="http://www.dsi.unifi.it/~merlini/poster.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.

%H Y. Baryshnikov, <a href="http://www.math.uiuc.edu/~ymb/texts/stokes.pdf">On Stokes sets</a>, New developments in singularity theory (Cambridge, 2000): 65-86. Kluwer Acad. Publ., Dordrecht, 2001.

%H 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 <a href="http://dx.doi.org/10.1007/BF02330563">Math. Annalen, 191 (1971), 87-98</a>.

%H L. W. Beineke and R. E. Pippert, <a href="http://dx.doi.org/10.4153/CJM-1974-006-x">Enumerating dissectable polyhedra by their automorphism groups</a>, Canad. J. Math., 26 (1974), 50-67.

%H Francois Bergeron, <a href="http://arxiv.org/abs/1202.6269">Combinatorics of r-Dyck paths, r-Parking functions, and the r-Tamari lattices</a>, arXiv:1202.6269 [math.CO], (3-March-2012)

%H Olivier Bernardi and Nicolas Bonichon, <a href="http://dx.doi.org/10.1016/j.jcta.2008.05.005">Intervals in Catalan lattices and realizers of triangulations</a>, Journal of Combinatorial Theory, Series A 116:1 (2009), pp. 55-75. See also Bernardi's slides, <a href="http://people.brandeis.edu/~bernardi/slides/slides-Tamari.pdf">Catalan lattices and realizers of triangulations</a> (April 2007).

%H D. Bevan, D. Levin, P. Nugent, J. Pantone, L. Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510:08036 [math.CO], 2015.

%H D. Birmajer, J. B. Gil, M. D. Weiner, <a href="http://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

%H Michel Bousquet and Cédric Lamathe, <a href="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1003">On symmetric structures of order two</a>, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.

%H M. Bousquet-Mélou and M. Petkovšek, <a href="https://arxiv.org/abs/math/0211432">Walks confined in a quadrant are not always D-finite</a>, arXiv:math/0211432 [math.CO], 2002.

%H N. T. Cameron, <a href="http://www.princeton.edu/~wmassey/NAM03/cameron.pdf">Random walks, trees and extensions of Riordan group techniques</a>

%H Naiomi Cameron, J. E. McLeod, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html">Returns and Hills on Generalized Dyck Paths</a>, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

%H L. Carlitz, <a href="http://www.fq.math.ca/Scanned/11-2/carlitz.pdf">Enumeration of two-line arrays</a>, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

%H F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/NCC-html/NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies in Automatic Combinatorics, Volume II (1997).

%H W. Y. C. Chen, T. Mansour and S. H. F. Yan, <a href="https://arxiv.org/abs/math/0504342">Matchings avoiding partial patterns</a>, arXiv:math/0504342 [math.CO], 2005.

%H J. Cigler, <a href="http://arxiv.org/abs/1312.2767">Some remarks about q-Chebyshev polynomials and q-Catalan numbers and related results</a>, arXiv:1312.2767 [math.CO], 2013.

%H T. C. Copeland, <a href="http://tcjpn.wordpress.com/2014/09/17/compositional-inverse-pairs-the-inviscid-burgers-hopf-equation-and-the-stasheff-associahedra/">Compositional inverse pairs, the Burgers-Hopf equation, and the Stasheff associahedra,</a>, 2014.

%H T. C. Copeland, <a href="http://tcjpn.wordpress.com/2012/06/13/depressed-equations-and-generalized-catalan-numbers/">Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers</a>, 2012.

%H S. J. Cyvin et al., <a href="http://dx.doi.org/10.1016/S0022-2860(97)00025-2">Staggered conformers of alkanes: complete solution of the enumeration problem</a>, J. Molec. Struct., 413 (1997), 227-239.

%H S. J. Cyvin et al., <a href="http://dx.doi.org/10.1016/S0022-2860(97)00419-5">Enumeration of staggered conformers of alkanes and monocyclic cycloalkanes</a>, J. Molec. Struct., 445 (1998), 127-13.

%H C. Defant and N. Kravitz, <a href="https://arxiv.org/abs/1809.09158">Stack-sorting for words</a>, arXiv:1809.09158 [math.CO], 2018.

%H E. Deutsch, S. Feretic and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00340-0">Diagonally convex directed polyominoes and even trees: a bijection and related issues</a>, Discrete Math., 256 (2002), 645-654.

%H S. Dulucq, <a href="/A005819/a005819.pdf">Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots</a>, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)

%H E. Deutsch and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00366-1">Statistics on non-crossing trees</a>, Discrete Math., 254 (2002), 75-87.

%H R. Dickau, <a href="http://robertdickau.com/fusscatalan.html">Fuss-Catalan Numbers</a>. Figures of various interpretations.

%H C. Domb and A. J. Barrett, <a href="http://dx.doi.org/10.1016/0012-365X(74)90081-8">Enumeration of ladder graphs</a>, Discrete Math. 9 (1974), 341-358.

%H C. Domb & A. J. Barrett, <a href="/A003408/a003408.pdf">Enumeration of ladder graphs</a>, Discrete Math. 9 (1974), 341-358. (Annotated scanned copy)

%H C. Domb & A. J. Barrett, <a href="/A001764/a001764.pdf">Notes on Table 2 in "Enumeration of ladder graphs"</a>, Discrete Math. 9 (1974), 55. (Annotated scanned copy)

%H J. A. Eidswick, <a href="http://dx.doi.org/10.1016/0012-365X(89)90266-5">Short factorizations of permutations into transpositions</a>, Disc. Math. 73 (1989) 239-243

%H Bryan Ek, <a href="https://arxiv.org/abs/1803.10920">Lattice Walk Enumeration</a>, arXiv:1803.10920 [math.CO], 2018.

%H Bryan Ek, <a href="https://arxiv.org/abs/1804.05933">Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics</a>, arXiv:1804.05933 [math.CO], 2018.

%H I. M. H. Etherington, <a href="http://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.

%H I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002639">Some problems of non-associative combinations</a>, Edinburgh Math. Notes, 32 (1940), 1-6.

%H I. M. H. Etherington, <a href="/A000108/a000108_14.pdf">Some problems of non-associative combinations (I)</a>, 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.

%H Jishe Feng, <a href="https://arxiv.org/abs/1810.09170">The Hessenberg matrices and Catalan and its generalized numbers</a>, arXiv:1810.09170 [math.CO], 2018. See p. 4.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 486

%H N. Gabriel, K. Peske, L. Pudwell, S. Tay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Pudwell/pudwell.html">Pattern Avoidance in Ternary Trees</a>, J. Int. Seq. 15 (2012) # 12.1.5

%H I. Gessel and G. Xin, <a href="https://arxiv.org/abs/math/0505217">The generating function of ternary trees and continued fractions</a>, arXiv:math/0505217 [math.CO], 2005.

%H N. S. S. Gu, N. Y. Li and T. Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%H F. Harary, E. M. Palmer, R. C. Read, <a href="/A000108/a000108_20.pdf">On the cell-growth problem for arbitrary polygons, computer printout, circa 1974</a>

%H T.-X. He, L. W. Shapiro, <a href="http://dx.doi.org/10.1016/j.laa.2017.06.025">Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group</a>, Lin. Alg. Applic. 532 (2017) 25-41, Fuss-Catalan Number (F_3)_n

%H V. E. Hoggatt, Jr., <a href="/A001628/a001628.pdf">Letters to N. J. A. Sloane, 1974-1975</a>

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="http://www.fq.math.ca/Scanned/14-5/hoggatt1.pdf">Catalan and related sequences arising from inverses of Pascal's triangle matrices</a>, Fib. Quart., 14 (1976), 395-405.

%H Vera M. Hur, M. A. Johnson, J. L. Martin, <a href="https://arxiv.org/abs/1609.02189">Oscillation estimates of eigenfunctions via the combinatorics of noncrossing partitions</a>, arXiv preprint arXiv:1609.02189 [math.SP], 2016.

%H Hsien-Kuei Hwang, Mihyun Kang, Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=53">Encyclopedia of Combinatorial Structures 53</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=285">Encyclopedia of Combinatorial Structures 285</a>

%H C. Ji, J. Propp, <a href="https://arxiv.org/abs/1805.03608">Brussels Sprouts, Noncrossing Trees, and Parking Functions</a>, arXiv preprint arXiv:1805.03608 [math.CO], 2018.

%H A. V. Kitaev, <a href="https://arxiv.org/abs/1809.00122">Meromorphic Solution of the Degenerate Third Painlevé Equation Vanishing at the Origin</a>, arXiv:1809.00122 [math.CA], 2018.

%H S. Kitaev and A. de Mier, <a href="http://arxiv.org/abs/1210.2618">Enumeration of fixed points of an involution on beta(1, 0)-trees</a>, arXiv preprint arXiv:1210.2618 [math.CO], 2012.

%H Don Knuth, <a href="https://www.youtube.com/watch?v=P4AaGQIo0HY">20th Anniversary Christmas Tree Lecture</a>

%H G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852).

%H D. V. Kruchinin, <a href="http://dx.doi.org/10.1186/s13662-014-0347-9">On solving some functional equations</a>, Advances in Difference Equations (2015) 2015:17; DOI 10.1186/s13662-014-0347-9.

%H Dmitry V. Kruchinin and Vladimir V. Kruchinin, <a href="http://www.emis.de/journals/JIS/VOL18/Kruchinin/kruch9.html">A Generating Function for the Diagonal T_{2n,n} in Triangles</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.6.

%H Markus Kuba and Alois Panholzer, <a href="http://dx.doi.org/10.1016/j.disc.2012.07.011">Enumeration formulas for pattern restricted Stirling permutations</a>, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012

%H W. Lang, <a href="http://www.itp.kit.edu/~wl/EISpub/A001764fig.pdf">Ternary trees with n=1,2,3 and 4 vertices. </a>

%H R. P. Loh, A. G. Shannon, A. F. Horadam, <a href="/A000969/a000969.pdf">Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients</a>, Preprint, 1980.

%H Lun Lv and Sabrina X.M. Pang, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p107">Reduced Decompositions of Matchings</a>, Electronic Journal of Combinatorics 18 (2011), #P107.

%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.1006/jcta.2002.3273">The tennis ball problem</a>, J. Combin. Theory, A 99 (2002), 307-344, (T_n for s=3).

%H Emanuele Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Munarini/muna4.html">Shifting Property for Riordan, Sheffer and Connection Constants Matrices</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.2.

%H W. Mlotkowski and K. A. Penson, <a href="http://arxiv.org/abs/1304.6544">The probability measure corresponding to 2-plane trees</a>, arXiv preprint arXiv:1304.6544 [math.PR], 2013.

%H H. Niederhausen, <a href="http://www.combinatorics.org/Volume_9/Abstracts/v9i1r33.html">Catalan Traffic at the Beach</a>.

%H J.-C. Novelli, J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014.

%H M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00121-0">Enumeration of noncrossing trees on a circle</a>, Discrete Math., 180, 301-313, 1998.

%H A. Panholzer and H. Prodinger, <a href="http://doi.org/10.1016/S0012-365X(01)00282-5">Bijections for ternary trees and non-crossing trees</a>, Discrete Math., 250 (2002), 181-195.

%H K. A. Penson and A. I. Solomon, <a href="http://arXiv.org/abs/quant-ph/0111151">Coherent states from combinatorial sequences</a>, arXiv:quant-ph/0111151, 2001.

%H K. H. Pilehrood, T. H. Pilehrood, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Pilehrood/pile5.html">Jacobi Polynomials and Congruences Involving Some Higher-Order Catalan Numbers and Binomial Coefficients</a>, J. Int. Seq. 18 (2015) 15.11.7.

%H Helmut Prodinger, <a href="https://doi.org/10.1016/j.disc.2008.01.035">A simple bijection between a subclass of 2-binary trees and ternary trees</a>, Discrete Mathematics 309.4 (2009): 959-961.

%H Jocelyn Quaintance, <a href="http://dx.doi.org/10.1016/j.disc.2006.09.041">Combinatoric Enumeration of Two-Dimensional Proper Arrays</a>, Discrete Math., 307 (2007), 1844-1864.

%H J. Riordan, <a href="/A001850/a001850_2.pdf">Letter, Jul 06 1978</a>

%H B. Rittaud, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rittaud2/rittaud11.html">On the Average Growth of Random Fibonacci Sequences</a>, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

%H A. Schuetz and G. Whieldon, <a href="http://arxiv.org/abs/1401.7194">Polygonal Dissections and Reversions of Series</a>, arXiv preprint arXiv:1401.7194 [math.CO], 2014.

%H Makoto Sekiyama, Toshiya Ohtsuki, Hiroshi Yamamoto, <a href="https://doi.org/10.7566/JPSJ.86.104003">Analytical Solution of Smoluchowski Equations in Aggregation-Fragmentation Processes</a>,

%H Journal of the Physical Society of Japan, 86.10, id 104003 (2017).

%H M. Somos, <a href="http://somos.crg4.com/nwic.html">Number Walls in Combinatorics</a>.

%H B Sury, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Sury/sury31.html">Generalized Catalan numbers: linear recursion and divisibility</a>, JIS 12 (2009) 09.7.5

%H S. Yakoubov, <a href="http://arxiv.org/abs/1310.2979">Pattern Avoidance in Extensions of Comb-Like Posets</a>, arXiv preprint arXiv:1310.2979 [math.CO], 2013.

%H Sheng-Liang Yang, LJ Wang, <a href="https://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p420.pdf">Taylor expansions for the m-Catalan numbers</a>, Australasian Journal of Combinatorics, Volume 64(3) (2016), Pages 420-431.

%H Anssi Yli-Jyra, <a href="http://dx.doi.org/10.1007/978-3-642-30773-7_10">On Dependency Analysis via Contractions and Weighted FSTs</a>, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158;

%H S.-n. Zheng and S.-l. Yang, <a href="http://dx.doi.org/10.1155/2014/848374">On the-Shifted Central Coefficients of Riordan Matrices</a>, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.

%H Jian Zhou, <a href="https://arxiv.org/abs/1810.03883">Fat and Thin Emergent Geometries of Hermitian One-Matrix Models</a>, arXiv:1810.03883 [math-ph], 2018.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F From _Karol A. Penson_, Nov 08 2001: (Start)

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

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

%F Integral representation as n-th moment of a positive function on [0, 27/4]: a(n) = Integral_{x=0..6.75} (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)))), n=0, 1, ... This representation is unique. (End)

%F G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2). - _Ralf Stephan_, Jun 30 2003

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

%F G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of). - _Paul Barry_, Mar 26 2010

%F From _Gary W. Adamson_, Jul 07 2011: (Start)

%F Let M = the production matrix:

%F 1, 1

%F 2, 2, 1

%F 3, 3, 2, 1

%F 4, 4, 3, 2, 1

%F 5, 5, 4, 3, 2, 1

%F ...

%F 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)

%F Recurrence: a(0)=1; a(n) = Sum_{i=0..n-1, j=0..n-1-i} a(i)a(j)a(n-1-i-j) for n >= 1 (counts ternary trees by subtrees of the root). - _David Callan_, Nov 21 2011

%F 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

%F 2*n*(2n+1)*a(n) - 3*(3n-1)*(3n-2)*a(n-1) = 0. - _R. J. Mathar_, Dec 14 2011

%F 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

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

%F 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

%F a(n) = binomial(3*n+1, n)/(3*n+1) = A062993(n+1,1). - _Robert FERREOL_, Apr 03 2015

%F 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

%F a(n) ~ 3^(3*n+1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). - _Ilya Gutkovskiy_, Nov 21 2016

%F Given g.f. A(x), then A(1/8) = -1 + sqrt(5), A(2/27) = (-1 + sqrt(3))*3/2, A(4/27) = 3/2, A(3/64) = -2 + 2*sqrt(7/3), A(5/64) = (-1 + sqrt(5))*2/sqrt(5), etc. A(n^2/(n+1)^3) = (n+1)/n if n > 1. - _Michael Somos_, Jul 17 2018

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

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

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

%p 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

%p 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

%p 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

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

%t Table[Binomial[3n,n]/(2n+1),{n,0,25}] (* _Harvey P. Dale_, Jul 24 2011 *)

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

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

%o (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))};

%o (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

%o (PARI) Vec(1 + serreverse(Ser(x / (1+x)^3 + O(x^30)))) \\ _Gheorghe Coserea_, Aug 05 2015

%o (Sage)

%o def A001764_list(n) :

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

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

%o for i in range(2*n) :

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

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

%o else : h += 1

%o b = not b

%o return R

%o A001764_list(22) # _Peter Luschny_, May 03 2012

%o (MAGMA) [Binomial(3*n,n)/(2*n+1): n in [0..30]]; // _Vincenzo Librandi_, Sep 04 2014

%o (Haskell)

%o a001764 n = a001764_list !! n

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

%o -- _Reinhard Zumkeller_, Jun 23 2015

%o (GAP) List([0..25],n->Binomial(3*n,n)/(2*n+1)); # _Muniru A Asiru_, Oct 31 2018

%Y Cf. A001762, A001763, A064017, A063548, A072247, A072248, A143603, A006013, A258708, A256311.

%Y A column of triangle A102537.

%Y Bisection of A047749 and A047761.

%Y Row sums of triangle A108410.

%Y Second column of triangle A062993.

%Y Cf. A134264.

%K easy,nonn,nice,core

%O 0,3

%A _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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 01:36 EST 2019. Contains 319260 sequences. (Running on oeis4.)