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

Author

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

Keywords

• nonn
• easy
• nice

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.

Crossrefs

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

Limit of array A102994.

Programs

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

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

PARI

a(n) = 3^n*binomial(2*n,n)/(n+1) \\ Charles R Greathouse IV, Feb 06 2017

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