|
%I M2927 N1175 #222 Sep 09 2023 08:44:03
%S 1,1,3,12,56,288,1584,9152,54912,339456,2149888,13891584,91287552,
%T 608583680,4107939840,28030648320,193100021760,1341536993280,
%U 9390758952960,66182491668480,469294031831040,3346270487838720,23981605162844160,172667557172477952
%N Number of rooted bicubic maps: a(n) = (8*n-4)*a(n-1)/(n+2) for n >= 2, a(0) = a(1) = 1.
%C Number of rooted Eulerian planar maps with n edges. - _Valery A. Liskovets_, Apr 07 2002
%C Number of indecomposable 1342-avoiding permutations of length n.
%C Also counts rooted planar 2-constellations with n digons. - _Valery A. Liskovets_, Dec 01 2003
%C 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
%C Number of "new" intervals in Tamari lattices of size n (see Chapoton paper). - _Ralf Stephan_, May 08 2007
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 321.
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000257/b000257.txt">Table of n, a(n) for n = 0..200</a>
%H Edward A. Bender and E. Rodney Canfield, <a href="http://dx.doi.org/10.1137/S0895480190177650">The number of degree restricted maps on the sphere</a>, SIAM J. Discr. Math., Vol. 7, No. 1 (1994), pp. 9-15.
%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.
%H Jonathan Bloom and Vince Vatter, <a href="https://arxiv.org/abs/1310.6073">Two Vignettes On Full Rook Placements</a>, arXiv preprint arXiv:1310.6073 [math.CO], 2013.
%H Miklós Bóna, <a href="https://arxiv.org/abs/math/9702223">Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps</a>, arXiv:math/9702223 [math.CO], 1997.
%H Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec, and Claire Pennarun, <a href="https://arxiv.org/abs/1610.09837">On the number of planar Eulerian orientations</a>, arXiv:1610.09837 [math.CO], 2016.
%H Nicolas Bonichon, Mireille Bousquet-Mélou, and Éric Fusy, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s61Abobofu.html">Baxter permutations and plane bipolar orientations</a> Sem. Lothar. Combin. 61A (2009/10), Art. B61Ah, 29 pp. See Section 8. - _N. J. A. Sloane_, Mar 27 2014
%H Valentin Bonzom, Guillaume Chapuy, Maciej Dolega, <a href="https://doi.org/10.5802/alco.268">Enumeration of non-oriented maps via integrability</a>, Alg. Combin. 5 (6) (2022) pp. 1363-1390, A.2.
%H Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, <a href="https://arxiv.org/abs/2303.10986">Refined product formulas for Tamari intervals</a>, arXiv:2303.10986 [math.CO], 2023.
%H 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 Mireille Bousquet-Mélou and G. Schaeffer, <a href="http://dx.doi.org/10.1006/aama.1999.0673">Enumeration of planar constellations</a>, Adv. in Appl. Math., Vol. 24, No. 4 (2000), pp. 337-368.
%H Frédéric Chapoton, <a href="https://arxiv.org/abs/math/0602368">Sur le nombre d'intervalles dans les treillis de Tamari</a>, arXiv:math/0602368 [math.CO], 2006.
%H P. Di Francesco, O. Golinelli and E. Guitter, <a href="https://arxiv.org/abs/hep-th/9602025">Meanders and the Temperley-Lieb algebra</a>, arXiv:hep-th/9602025, 1996; see Eq. C.1.
%H Wenjie Fang, <a href="https://arxiv.org/abs/2001.04723">Bijective link between Chapoton's new intervals and bipartite planar maps</a>, arXiv:2001.04723 [math.CO], 2020.
%H Alice L.L. Gao, Sergey Kitaev, and Philip B. Zhang, <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.
%H Juan B. Gil, David Kenepp, and Michael Weiner, <a href="https://permutationpatterns.com/files/2020/06/WednesdayA_Gil.pdf">Pattern-avoiding permutations by inactive sites</a>, Pennsylvania State University, Altoona (2020).
%H 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 Christian Kassel and Christophe Reutenauer, <a href="https://arxiv.org/abs/1303.3481">Algebraicity of the zeta function associated to a matrix over a free group algebra</a>, arXiv:1303.3481 [math.CO], 2013-2014.
%H Philippe Leroux, <a href="https://arxiv.org/abs/math/0512437">A simple symmetry generating operads related to rooted planar m-ary trees and polygonal numbers</a>, arXiv:math/0512437 [math.CO], 2005.
%H Zhaoxiang Li and Yanpei Liu, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.039">Chromatic sums of general maps on the sphere and the projective plane</a>, Discr. Math., Vol. 307, No. 1 (2007), pp. 78-87.
%H Valery A. Liskovets and Timothy R. S. Walsh, <a href="http://dx.doi.org/10.1016/j.disc.2003.09.015">Enumeration of Eulerian and unicursal planar maps</a>, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.
%H Alexander Mednykh and Roman Nedela, <a href="http://www-igm.univ-mlv.fr/~fpsac/FPSAC06/SITE06/papers/09.pdf">Counting unrooted hypermaps on closed orientable surface</a>, 18th Intern. Conf. Formal Power Series & Algebr. Comb., Jun 19, 2006, San Diego, California (USA).
%H Alexander Mednykh and Roman Nedela, <a href="http://dx.doi.org/10.1016/j.disc.2009.03.033">Enumeration of unrooted hypermaps of a given genus</a>, Discr. Math., Vol. 310, No. 3 (2010), pp. 518-526. [From _N. J. A. Sloane_, Dec 19 2009]
%H Mednykh, A.; Nedela, R. <a href="https://doi.org/10.1007/s10958-017-3555-5">Recent progress in enumeration of hypermaps</a>, J. Math. Sci., New York 226, No. 5, 635-654 (2017) and Zap. Nauchn. Semin. POMI 446, 139-164 (2016). Table 2
%H Wojciech Mlotkowski and Karol A. Penson, <a href="https://arxiv.org/abs/1507.07312">A Fuss-type family of positive definite sequences</a>, arXiv:1507.07312 [math.PR], 2015.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992, arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0912.0072">Une méthode pour obtenir la fonction génératrice d'une série.</a>, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
%H W. T. Tutte, <a href="http://dx.doi.org/10.4153/CJM-1963-029-x">A Census of Planar Maps</a>, Canad. J. Math., Vol. 15 (1963), pp. 249-271.
%H T. R. S. Walsh, <a href="http://dx.doi.org/10.1016/0095-8956(75)90042-8">Hypermaps versus bipartite maps</a>, J. Combin. Th., Series B, Vol. 18, No. 2 (1975), pp. 155-163.
%H Timothy R. Walsh, <a href="http://www.info2.uqam.ca/~walsh_t/papers/GENERATING NONISOMORPHIC.pdf">Space-efficient generation of nonisomorphic maps and hypermaps</a>.
%H T. R. Walsh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Walsh/walsh3.html">Space-Efficient Generation of Nonisomorphic Maps and Hypermaps</a>, J. Int. Seq., Vol. 18 (2015), Article 15.4.3.
%H Peter G. Zograf, <a href="https://doi.org/10.1093/imrn/rnv077">Enumeration of Grothendieck's Dessins and KP Hierarchy</a>, International Mathematics Research Notices, Volume 2015, Issue 24 (1 January 2015), pp. 13533-13544.
%F a(0) = 1 and a(n) = 3*2^(n-1)*C(n)/(n+2) for n >= 1, where C = Catalan (A000108).
%F a(n) = 2^(n-2) * A007054(n), n > 1.
%F 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
%F 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
%F O.g.f.: 1 + x*2F1( (1, 3/2); (4); 8*x). - _Olivier Gérard_, Feb 15 2011
%F D-finite with recurrence (n + 2) * a(n) = (8*n - 4) * a(n - 1). - _Simon Plouffe_, Feb 09 2012
%F 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
%F a(n) ~ 3*2^(3*n-1) / (sqrt(Pi)*n^(5/2)). - _Vaclav Kotesovec_, Mar 10 2014
%F 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
%F 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
%F 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
%F 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
%F From _Amiram Eldar_, Mar 22 2022: (Start)
%F Sum_{n>=0} 1/a(n) = 1985/1029 + 1280*arcsin(1/(2*sqrt(2)))/(343*sqrt(7)).
%F Sum_{n>=0} (-1)^n/a(n) = 341/729 - 1280*arcsinh(1/(2*sqrt(2)))/2187. (End)
%e G.f. = 1 + x + 3*x^2 + 12*x^3 + 56*x^4 + 288*x^5 + 1584*x^6 + 9152*x^7 + ...
%p A000257 := proc(n)
%p option remember;
%p if n <=1 then
%p 1;
%p else
%p 4*(2*n-1)*procname(n-1)/(n+2) ;
%p end if ;
%p end proc: # _R. J. Mathar_, Dec 18 2011
%t CoefficientList[Series[1 + x HypergeometricPFQ[{1, 3/2}, {4}, 8 x], {x, 0, 10}], x]
%t (* Second program: *)
%t Join[{1}, Table[3*2^(n-1) CatalanNumber[n]/(n+2), {n, 30}]] (* _Harvey P. Dale_, Dec 18 2011 *)
%o (PARI)
%o C(n)=binomial(2*n, n)/(n+1);
%o a(n)=if(n==0, 1, 3*2^(n-1)*C(n)/(n+2) ); \\ _Joerg Arndt_, May 04 2013
%o (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
%o (PARI)
%o x='x; y='y; Fxy = 16*x^2*y^2 - (8*x^2+12*x-1)*y + x^2+11*x-1;
%o seq(N) = {
%o my(y0 = 1 + O('x^N), y1=0);
%o for (k = 1, N,
%o y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
%o if (y1 == y0, break()); y0 = y1);
%o Vec(y0);
%o };
%o seq(24) \\ _Gheorghe Coserea_, Nov 30 2016
%o (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
%o (Python)
%o a000257 = [1]
%o for n in range(1, 25): a000257.append((8*n-4)*a000257[-1]//(n+2))
%o print(a000257) # _Gennady Eremin_, Mar 22 2022
%Y Cf. A069726, A007054, A298358 (rooted).
%Y First row of array A101477.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
| 