cp's OEIS Frontend

A005159 a(n) = 3^n*Catalan(n).

%I A005159 #146 Apr 20 2025 20:13:13
%S A005159 1,3,18,135,1134,10206,96228,938223,9382230,95698746,991787004,
%T A005159 10413763542,110546105292,1184422556700,12791763612360,
%U A005159 139110429284415,1522031755700070,16742349312700770,185047018719324300,2054021907784499730
%N A005159 a(n) = 3^n*Catalan(n).
%C A005159 Total number of vertices in rooted planar maps with n edges.
%C A005159 Number of blossom trees with n inner vertices.
%C A005159 The number of rooted n-edge maps in the plane (planar with a distinguished outside face). - _Valery A. Liskovets_, Mar 17 2005
%C A005159 Hankel transform is 3^(n+n^2) = A053764(n+1). - _Philippe Deléham_, Dec 10 2007
%C A005159 From _Joerg Arndt_, Oct 22 2012: (Start)
%C A005159 Also the number of strings of length 2*n of three different types of balanced parentheses.
%C A005159 The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)
%C A005159 Number of Dyck paths of length 2n in which the step U=(1,1) come in 3 colors. - _José Luis Ramírez Ramírez_, Jan 31 2013
%C A005159 Number of unknown entries in bracketed Kleene's truth table connected by the implication with n distinct variables. See Yildiz link. - _Michel Marcus_, Oct 21 2020
%D A005159 Leonid M. Koganov, Valery A. Liskovets and Timothy R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin., Vol. 54 (2000), pp. 149-160.
%D A005159 Valery A. Liskovets and Timothy R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.
%D A005159 Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 107.
%H A005159 T. D. Noe, <a href="/A005159/b005159.txt">Table of n, a(n) for n = 0..100</a>
%H A005159 Mireille Bousquet-Mélou, <a href="https://arxiv.org/abs/math/0501266">Limit laws for embedded trees</a>, arXiv:math/0501266 [math.CO], 2005.
%H A005159 J. Bouttier, P. Di Francesco and E. Guitter, <a href="http://dx.doi.org/10.1016/j.nuclphysb.2003.09.046">Statistics of planar graphs viewed from a vertex: a study via labeled trees</a>, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).
%H A005159 Zhi Chen and Hao Pan, <a href="http://arxiv.org/abs/1608.02448">Identities involving weighted Catalan-Schroder and Motzkin Paths</a>, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=3.
%H A005159 Aoife Hennessy, <a href="http://repository.wit.ie/1693/">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H A005159 Gerard 't Hooft, <a href="https://doi.org/10.1016/S0550-3213(98)00697-X">Counting planar diagrams with various restrictions</a>, Nucl. Phys. B, Vol. 538, No. 1-2 (1999), pp. 389-410; <a href="http://arxiv.org/abs/hep-th/9808113">arXiv:hep preprint</a> arXiv:hep-th/9808113, 1998.
%H A005159 Hsien-Kuei Hwang, Mihyun Kang and 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 A005159 Sergey Kitaev, Anna de Mier and Marc Noy, <a href="http://dx.doi.org/10.1016/j.ejc.2013.06.013">On the number of self-dual rooted maps</a>, European J. Combin., Vol. 35 (2014), pp. 377-387. MR3090510.
%H A005159 Valery A. Liskovets, <a href="http://dx.doi.org/10.1006/jctb.1998.1870">A pattern of asymptotic vertex valency distributions in planar maps</a>, J. Combin. Th. B, Vol. 75, No. 1 (1999), pp. 116-133.
%H A005159 Valery A. Liskovets and T. R. Walsh, <a href="http://dx.doi.org/10.1016/j.aam.2005.03.006">Counting unrooted maps on the plane</a>, Advances in Applied Math., Vol. 36, No. 4 (2006), pp. 364-387.
%H A005159 Thomas M. Richardson, <a href="http://arxiv.org/abs/1609.01193">The three 'R's and Dual Riordan Arrays</a>, arXiv:1609.01193 [math.CO], 2016.
%H A005159 Gilles Schaeffer and Paul Zinn-Justin, <a href="http://arXiv.org/abs/math-ph/0304034">On the asymptotic number of plane curves and alternating knots</a>, arXiv:math-ph/0304034, 2003-2004.
%H A005159 Simeon T. Stefanov, <a href="https://arxiv.org/abs/1807.03714">Counting fixed points free vector fields on B^2</a>, arXiv:1807.03714 [math.GT], 2018.
%H A005159 Volkan Yildiz, <a href="https://arxiv.org/abs/2010.10303">Counting with 3-valued truth tables of bracketed formulae connected by implication</a>, arXiv:2010.10303 [math.GM], 2020.
%F A005159 G.f.: 2/(1+sqrt(1-12x)) = (1 - sqrt(1-4*(3*x))) / (6*x).
%F A005159 With offset 1 : a(1)=1, a(n) = 3*Sum_{i=1..n-1} a(i)*a(n-i). - _Benoit Cloitre_, Mar 16 2004
%F A005159 G.f.: c(3*x) with c(x) the o.g.f. of A000108 (Catalan).
%F A005159 From _Gary W. Adamson_, Jul 12 2011: (Start)
%F A005159 a(n) is the upper left term in M^n, M = the infinite square production matrix:
%F A005159   3, 3, 0, 0, 0, 0, ...
%F A005159   3, 3, 3, 0, 0, 0, ...
%F A005159   3, 3, 3, 3, 0, 0, ...
%F A005159   3, 3, 3, 3, 3, 0, ...
%F A005159   3, 3, 3, 3, 3, 3, ...
%F A005159   ... (End)
%F A005159 D-finite with recurrence (n+1)*a(n)+6*(1-2n)*a(n-1)=0. - _R. J. Mathar_, Apr 01 2012
%F A005159 E.g.f.: a(n) = n!* [x^n] KummerM(1/2, 2, 12*x). - _Peter Luschny_, Aug 25 2012
%F A005159 a(n) = sum_{k=0..n} A085880(n,k)*2^k. - _Philippe Deléham_, Nov 15 2013
%F A005159 From _Ilya Gutkovskiy_, Dec 04 2016: (Start)
%F A005159 E.g.f.: (BesselI(0,6*x) - BesselI(1,6*x))*exp(6*x).
%F A005159 a(n) ~ 12^n/(sqrt(Pi)*n^(3/2)). (End)
%F A005159 a(n) = A000244(n)*A000108(n). - _Omar E. Pol_, Mar 30 2018
%F A005159 Sum_{n>=0} 1/a(n) = 150/121 + 216*arctan(1/sqrt(11)) / (121*sqrt(11)). - _Vaclav Kotesovec_, Nov 23 2021
%F A005159 Sum_{n>=0} (-1)^n/a(n) = 138/169 - 216*arctanh(1/sqrt(13)) / (169*sqrt(13)). - _Amiram Eldar_, Jan 25 2022
%F A005159 G.f.: 1/(1-3*x/(1-3*x/(1-3*x/(1-3*x/(1-3*x/(1-3*x/(1-3*x/(1-3*x/(1-...))))))))) (continued fraction). - _Nikolaos Pantelidis_, Nov 20 2022
%p A005159 A005159_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
%p A005159 for w from 1 to n do a[w] := 3*(a[w-1]+add(a[j]*a[w-j-1],j=1..w-1)) od;convert(a,list)end: A005159_list(19); # _Peter Luschny_, May 19 2011
%t A005159 InverseSeries[Series[y-3*y^2, {y, 0, 24}], x] (* then A(x)=y(x)/x *) (* _Len Smiley_, Apr 07 2000 *)
%t A005159 Table[3^n CatalanNumber[n],{n,0,30}] (* _Harvey P. Dale_, May 18 2011 *)
%t A005159 CoefficientList[Series[(1 - Sqrt[1-4*(3*x)])/(6*x), {x, 0, 50}], x] (* _Stefano Spezia_, Oct 16 2018 *)
%o A005159 (PARI) a(n) = 3^n*binomial(2*n,n)/(n+1) \\ _Charles R Greathouse IV_, Feb 06 2017
%o A005159 (GAP) List([0..20],n->3^n*Binomial(2*n,n)/(n+1)); # _Muniru A Asiru_, Mar 30 2018
%o A005159 (Magma) [3^n*Catalan(n): n in [0..20]]; // _Vincenzo Librandi_, Oct 16 2018
%Y A005159 Cf. A000108, A000244, A025226, A053764, A085880.
%Y A005159 Limit of array A102994.
%K A005159 nonn,easy,nice
%O A005159 0,2
%A A005159 _N. J. A. Sloane_, _Valery A. Liskovets_