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

1, 3, 18, 135, 1134, 10206, 96228, 938223, 9382230, 95698746, 991787004, 10413763542, 110546105292, 1184422556700, 12791763612360, 139110429284415, 1522031755700070, 16742349312700770, 185047018719324300, 2054021907784499730

Offset

0,2

Comments

Total number of vertices in rooted planar maps with n edges.

Number of blossom trees with n inner vertices.

The number of rooted n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005

Hankel transform is 3^(n+n^2) = A053764(n+1). - Philippe Deléham, Dec 10 2007

From Joerg Arndt, Oct 22 2012: (Start)

Also the number of strings of length 2*n of three different types of balanced parentheses.

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)

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

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

References

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.

Valery A. Liskovets and Timothy R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 107.

Links

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

Mireille Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.

J. Bouttier, P. Di Francesco and E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).

Zhi Chen and Hao Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=3.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Gerard 't Hooft, Counting planar diagrams with various restrictions, Nucl. Phys. B, Vol. 538, No. 1-2 (1999), pp. 389-410; arXiv:hep preprint arXiv:hep-th/9808113, 1998.

Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

Sergey Kitaev, Anna de Mier and Marc Noy, On the number of self-dual rooted maps, European J. Combin., Vol. 35 (2014), pp. 377-387. MR3090510.

Valery A. Liskovets, A pattern of asymptotic vertex valency distributions in planar maps, J. Combin. Th. B, Vol. 75, No. 1 (1999), pp. 116-133.

Valery A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., Vol. 36, No. 4 (2006), pp. 364-387.

Thomas M. Richardson, The three 'R's and Dual Riordan Arrays, arXiv:1609.01193 [math.CO], 2016.

Gilles Schaeffer and Paul Zinn-Justin, On the asymptotic number of plane curves and alternating knots, arXiv:math-ph/0304034, 2003-2004.

Simeon T. Stefanov, Counting fixed points free vector fields on B^2, arXiv:1807.03714 [math.GT], 2018.

Volkan Yildiz, Counting with 3-valued truth tables of bracketed formulae connected by implication, arXiv:2010.10303 [math.GM], 2020.

Formula

G.f.: 2/(1+sqrt(1-12x)) = (1 - sqrt(1-4*(3*x))) / (6*x).

With offset 1 : a(1)=1, a(n) = 3*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004

G.f.: c(3*x) with c(x) the o.g.f. of A000108 (Catalan).

From Gary W. Adamson, Jul 12 2011: (Start)

a(n) is the upper left term in M^n, M = the infinite square production matrix:

3, 3, 0, 0, 0, 0, ...

3, 3, 3, 0, 0, 0, ...

3, 3, 3, 3, 0, 0, ...

3, 3, 3, 3, 3, 0, ...

3, 3, 3, 3, 3, 3, ...

... (End)

D-finite with recurrence (n+1)*a(n)+6*(1-2n)*a(n-1)=0. - R. J. Mathar, Apr 01 2012

E.g.f.: a(n) = n!* [x^n] KummerM(1/2, 2, 12*x). - Peter Luschny, Aug 25 2012

a(n) = sum_{k=0..n} A085880(n,k)*2^k. - Philippe Deléham, Nov 15 2013

From Ilya Gutkovskiy, Dec 04 2016: (Start)

E.g.f.: (BesselI(0,6*x) - BesselI(1,6*x))*exp(6*x).

a(n) ~ 12^n/(sqrt(Pi)*n^(3/2)). (End)

a(n) = A000244(n)*A000108(n). - Omar E. Pol, Mar 30 2018

Sum_{n>=0} 1/a(n) = 150/121 + 216*arctan(1/sqrt(11)) / (121*sqrt(11)). - Vaclav Kotesovec, Nov 23 2021

Sum_{n>=0} (-1)^n/a(n) = 138/169 - 216*arctanh(1/sqrt(13)) / (169*sqrt(13)). - Amiram Eldar, Jan 25 2022

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

Maple

A005159_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
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

Mathematica

InverseSeries[Series[y-3*y^2, {y, 0, 24}], x] (* then A(x)=y(x)/x *) (* Len Smiley, Apr 07 2000 *)
Table[3^n CatalanNumber[n], {n, 0, 30}] (* Harvey P. Dale, May 18 2011 *)
CoefficientList[Series[(1 - Sqrt[1-4*(3*x)])/(6*x), {x, 0, 50}], x] (* Stefano Spezia, Oct 16 2018 *)

Prog

(PARI) a(n) = 3^n*binomial(2*n, n)/(n+1) \\ Charles R Greathouse IV, Feb 06 2017
(GAP) List([0..20], n->3^n*Binomial(2*n, n)/(n+1)); # Muniru A Asiru, Mar 30 2018
(Magma) [3^n*Catalan(n): n in [0..20]]; // Vincenzo Librandi, Oct 16 2018

Crossrefs

Cf. A000108, A000244, A025226, A053764, A085880.

Limit of array A102994.

Sequence in context: A355105 A095776 A114178 * A151383 A177406 A289430

Adjacent sequences: A005156 A005157 A005158 * A005160 A005161 A005162

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Valery A. Liskovets

Status

approved