A000257 Number of rooted bicubic maps: a(n) = (8*n-4)*a(n-1)/(n+2) for n >= 2, a(0) = a(1) = 1.

1, 1, 3, 12, 56, 288, 1584, 9152, 54912, 339456, 2149888, 13891584, 91287552, 608583680, 4107939840, 28030648320, 193100021760, 1341536993280, 9390758952960, 66182491668480, 469294031831040, 3346270487838720, 23981605162844160, 172667557172477952

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Number of rooted Eulerian planar maps with n edges. - Valery A. Liskovets, Apr 07 2002

Number of indecomposable 1342-avoiding permutations of length n.

Also counts rooted planar 2-constellations with n digons. - Valery A. Liskovets, Dec 01 2003

a(n) is also the number of rooted planar hypermaps with n darts (darts are semi-edges in the particular case of ordinary maps). - Valery A. Liskovets, Apr 13 2006

Number of "new" intervals in Tamari lattices of size n (see Chapoton paper). - Ralf Stephan, May 08 2007

Examples

			G.f. = 1 + x + 3*x^2 + 12*x^3 + 56*x^4 + 288*x^5 + 1584*x^6 + 9152*x^7 + ...
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 321.
• L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin., Vol. 54 (2000), pp. 149-160.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• Edward A. Bender and E. Rodney Canfield, The number of degree restricted maps on the sphere, SIAM J. Discr. Math., Vol. 7, No. 1 (1994), pp. 9-15.
• Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
• Jonathan Bloom and Vince Vatter, Two Vignettes On Full Rook Placements, arXiv preprint arXiv:1310.6073 [math.CO], 2013.
• Miklós Bóna, Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, arXiv:math/9702223 [math.CO], 1997.
• Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec, and Claire Pennarun, On the number of planar Eulerian orientations, arXiv:1610.09837 [math.CO], 2016.
• Nicolas Bonichon, Mireille Bousquet-Mélou, and Éric Fusy, Baxter permutations and plane bipolar orientations Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp. See Section 8. - _N. J. A. Sloane_, Mar 27 2014
• Valentin Bonzom, Guillaume Chapuy, and Maciej Dolega, Enumeration of non-oriented maps via integrability, Alg. Combin. 5 (6) (2022) pp. 1363-1390, A.2.
• Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, Refined product formulas for Tamari intervals, arXiv:2303.10986 [math.CO], 2023.
• Mireille Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.
• Mireille Bousquet-Mélou and G. Schaeffer, Enumeration of planar constellations, Adv. in Appl. Math., Vol. 24, No. 4 (2000), pp. 337-368.
• Frédéric Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, arXiv:math/0602368 [math.CO], 2006.
• P. Di Francesco, O. Golinelli and E. Guitter, Meanders and the Temperley-Lieb algebra, arXiv:hep-th/9602025, 1996; see Eq. C.1.
• Wenjie Fang, Bijective link between Chapoton's new intervals and bipartite planar maps, arXiv:2001.04723 [math.CO], 2020.
• Alice L.L. Gao, Sergey Kitaev, and Philip B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
• Juan B. Gil, David Kenepp, and Michael Weiner, Pattern-avoiding permutations by inactive sites, Pennsylvania State University, Altoona (2020).
• 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.
• Christian Kassel and Christophe Reutenauer, Algebraicity of the zeta function associated to a matrix over a free group algebra, arXiv:1303.3481 [math.CO], 2013-2014.
• Philippe Leroux, A simple symmetry generating operads related to rooted planar m-ary trees and polygonal numbers, arXiv:math/0512437 [math.CO], 2005.
• Zhaoxiang Li and Yanpei Liu, Chromatic sums of general maps on the sphere and the projective plane, Discr. Math., Vol. 307, No. 1 (2007), pp. 78-87.
• Valery A. Liskovets and Timothy R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.
• Alexander Mednykh and Roman Nedela, Counting unrooted hypermaps on closed orientable surface, 18th Intern. Conf. Formal Power Series & Algebr. Comb., Jun 19, 2006, San Diego, California (USA).
• Alexander Mednykh and Roman Nedela, Enumeration of unrooted hypermaps of a given genus, Discr. Math., Vol. 310, No. 3 (2010), pp. 518-526. [From _N. J. A. Sloane_, Dec 19 2009]
• Mednykh, A.; Nedela, R. Recent progress in enumeration of hypermaps, J. Math. Sci., New York 226, No. 5, 635-654 (2017) and Zap. Nauchn. Semin. POMI 446, 139-164 (2016). Table 2
• Wojciech Mlotkowski and Karol A. Penson, A Fuss-type family of positive definite sequences, arXiv:1507.07312 [math.PR], 2015.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992, arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série., arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
• W. T. Tutte, A Census of Planar Maps, Canad. J. Math., Vol. 15 (1963), pp. 249-271.
• T. R. S. Walsh, Hypermaps versus bipartite maps, J. Combin. Th., Series B, Vol. 18, No. 2 (1975), pp. 155-163.
• Timothy R. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps.
• T. R. Walsh, Space-Efficient Generation of Nonisomorphic Maps and Hypermaps, J. Int. Seq., Vol. 18 (2015), Article 15.4.3.
• Peter G. Zograf, Enumeration of Grothendieck's Dessins and KP Hierarchy, International Mathematics Research Notices, Volume 2015, Issue 24 (1 January 2015), pp. 13533-13544.

Crossrefs

Cf. A069726, A007054, A298358 (rooted).

First row of array A101477.

Programs

Magma

[1] cat [3*2^n*Factorial(2*n)/((2*n^2+6*n+4)*Factorial(n)^2): n in [1.. 25]]; // Vincenzo Librandi, Oct 21 2014

Maple

A000257 := proc(n)
        option remember;
        if n <=1 then
                1;
        else
                4*(2*n-1)*procname(n-1)/(n+2) ;
        end if ;
end proc: # R. J. Mathar, Dec 18 2011

Mathematica

CoefficientList[Series[1 + x HypergeometricPFQ[{1, 3/2}, {4}, 8 x], {x, 0, 10}], x]
(* Second program: *)
Join[{1}, Table[3*2^(n-1) CatalanNumber[n]/(n+2), {n, 30}]] (* Harvey P. Dale, Dec 18 2011 *)

PARI

C(n)=binomial(2*n, n)/(n+1);
a(n)=if(n==0, 1, 3*2^(n-1)*C(n)/(n+2) ); \\ Joerg Arndt, May 04 2013

PARI

x='x+O('x^66); Vec( ((1-8*x)^(3/2) + 8*x^2 + 12*x - 1)/(32*x^2) ) \\ Joerg Arndt, May 04 2013

PARI

x='x; y='y; Fxy = 16*x^2*y^2 - (8*x^2+12*x-1)*y + x^2+11*x-1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(24) \\ Gheorghe Coserea, Nov 30 2016

Python

a000257 = [1]
for n in range(1, 25): a000257.append((8*n-4)*a000257[-1]//(n+2))
print(a000257) # Gennady Eremin, Mar 22 2022

Formula

a(0) = 1 and a(n) = 3*2^(n-1)*C(n)/(n+2) for n >= 1, where C = Catalan (A000108).

a(n) = 2^(n-2) * A007054(n), n > 1.

O.g.f.: 1/4 + (1/8) * ( -(1-8*x)^(1/2) + 16*(1-8*x)^(1/2)*x+1-8*x ) / ((1-8*x)^(1/2)*x*(1+(1-8*x)^(1/2))). - Karol A. Penson, Jun 04 2004

E.g.f.: (1/8) * exp(4*x)*(8*BesselI(0, 4*x)*x-BesselI(1, 4*x)-8*BesselI(1, 4*x)*x)/x. - Karol A. Penson, Jun 04 2004

O.g.f.: 1 + x*2F1( (1, 3/2); (4); 8*x). - Olivier Gérard, Feb 15 2011

D-finite with recurrence (n + 2) * a(n) = (8*n - 4) * a(n - 1). - Simon Plouffe, Feb 09 2012

O.g.f.: ((1-8*x)^(3/2) + 8*x^2 + 12*x - 1)/(32*x^2) = 1 + x + 3*x^2 + 12*x^3 + 56*x^4 + .... The related generating function 1 + 3*x^2 + 12*x^4 + 56*x^6 + ... is the zeta function associated to a certain 2 X 2 matrix of noncommuting variables. See Kassel and Reutenauer, Example 5.1. - Peter Bala, Mar 15 2013

a(n) ~ 3*2^(3*n-1) / (sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Mar 10 2014

0 = a(n) * (64*a(n+1) - 28*a(n+2)) + a(n+1) * (12*a(n+1) + a(n+2)) if n > 0. - Michael Somos, Apr 03 2014

Integral representation as the n-th moment of the positive function W(x) on (0,8). a(n) = Integral_{x=0..8} x^n*W(x) dx, n=1,2,3,..., where W(x) = sqrt((8-x)^3/x)/(32*Pi). For n=0 the integral is equal to 3/4. This means that a(n) is the n-th moment, n=0,1,2,..., of the probability distribution which is a sum of W(x) as the continuous part and an atom at x=0 with weight 1/4 (Dirac(x)/4). This representation is unique as W(x) is the solution of the Hausdorff moment problem. - Karol A. Penson and Wojciech Mlotkowski, Jul 15 2015

G.f. y satisfies: 0 = 16*x^2*y^2 - (8*x^2+12*x-1)*y + x^2+11*x-1. - Gheorghe Coserea, Nov 22 2016

A(x) = (1 + 4*y - y^2)/4, where y = C(2*x), C being the g.f. for A000108. - Gheorghe Coserea, Apr 10 2018

From Amiram Eldar, Mar 22 2022: (Start)

Sum_{n>=0} 1/a(n) = 1985/1029 + 1280*arcsin(1/(2*sqrt(2)))/(343*sqrt(7)).

Sum_{n>=0} (-1)^n/a(n) = 341/729 - 1280*arcsinh(1/(2*sqrt(2)))/2187. (End)

O.g.f.: x*A(x) is the compositional inverse of x - x^2*B(x), where B(x) is the o.g.f. of A165546. - Alexander Burstein, Aug 02 2024