login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005159 a(n) = 3^n*Catalan(n). 23
1, 3, 18, 135, 1134, 10206, 96228, 938223, 9382230, 95698746, 991787004, 10413763542, 110546105292, 1184422556700, 12791763612360, 139110429284415, 1522031755700070, 16742349312700770, 185047018719324300, 2054021907784499730 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.

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

LINKS

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

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

Z. Chen, H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 (2016), 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

G. 't Hooft, Counting planar diagrams with various restrictions, Nucl. Phys. B538 (1999), 389-410.

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

V. A. Liskovets, A pattern of asymptotic vertex valency distributions in planar maps, J. Combin. Th., B75 (1999), 116-133.

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

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

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

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

a(n) = 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, ...

...

- Gary W. Adamson, Jul 12 2011

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

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

PROG

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

CROSSREFS

Cf. A000108, A025226.

Limit of array A102994.

Sequence in context: A251733 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 18 16:31 EDT 2017. Contains 293524 sequences.