A066537 - OEIS

%I #39 Feb 05 2020 23:51:31

%S 1,1,2,8,64,1023,32071,1823707,163947848,20402420291,3209997749284,

%T 604611323732576,131861300077834966,32577569614176693919,

%U 8977083127683999891824,2726955513946123452637877,904755724004585279250537376,325403988657293080813790670641

%N Number of planar graphs on n labeled nodes.

%C Precise numbers derived from numbers of 3-connected, 2-connected and 1-connected planar labeled graphs. Details and more entries in Bodirsky et al. Some bounds on the asymptotics are known, see e.g. Taraz et al.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 419.

%H Keith M. Briggs and Gheorghe Coserea, <a href="/A066537/b066537.txt">Table of n, a(n) for n = 0..126</a>, terms 0..42 from Keith M. Briggs.

%H M. Bodirsky, C. Groepl and M. Kang, <a href="http://dx.doi.org/10.1007/3-540-45061-0_84">Generating Labeled Planar Graphs Uniformly At Random</a>, ICALP03 Eindhoven, LNCS 2719, Springer Verlag (2003), 1095 - 1107.

%H M. Bodirsky, C. Groepl and M. Kang, <a href="http://dx.doi.org/10.1016/j.tcs.2007.02.045">Generating Labeled Planar Graphs Uniformly At Random</a>, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, Pages 377-386.

%H Keith M. Briggs, <a href="http://keithbriggs.info/cgt.html">Combinatorial Graph Theory</a>

%H O. Gimenez and M. Noy, <a href="https://arxiv.org/abs/math/0501269">Asymptotic enumeration and limit laws of planar graphs</a>, arXiv:math/0501269 [math.CO], 2005.

%H Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato, <a href="https://arxiv.org/abs/1911.07465">Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration</a>, arXiv:1911.07465 [cs.DS], 2019.

%H A. Taraz, D. Osthus and H. J. Proemel, <a href="http://dx.doi.org/10.1016/S0095-8956(02)00040-0">On random planar graphs, the number of planar graphs and their triangulations</a> Journal of Combinatorial Theory, Series B, 88 (2003), 119-134.

%F Recurrence known, see Bodirsky et al.

%F a(n) ~ g * n^(-7/2) * gamma^n * n!, where g=0.000004260938569161439...(A266391) and gamma=27.2268777685...(A266390) (see Gimenez and Noy).

%o (PARI)

%o Q(n,k) = { \\ c-nets with n-edges, k-vertices

%o   if (k < 2+(n+2)\3 || k > 2*n\3, return(0));

%o   sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k,i)*i*(i-1)/2*

%o   (binomial(2*n-2*k+2,k-i)*binomial(2*k-2, n-j) -

%o   4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));

%o };

%o A100960_ser(N) = {

%o my(x='x+O('x^(3*N+1)), t='t+O('t^(N+4)),

%o    q=t*x*Ser(vector(3*N+1, n, Polrev(vector(min(N+3, 2*n\3), k, Q(n,k)),'t))),

%o    d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),

%o    g2=intformal(t^2/2*((1+d)/(1+x)-1)));

%o    serlaplace(Ser(vector(N, n, subst(polcoeff(g2, n,'t),'x,'t)))*'x);

%o };

%o A096331_seq(N) = Vec(subst(A100960_ser(N+2),'t,1));

%o A096332_seq(N) = {

%o   my(x='x+O('x^(N+3)), b=x^2/2+serconvol(Ser(A096331_seq(N))*x^3, exp(x)));

%o   Vec(serlaplace(intformal(serreverse(x/exp(b'))/x)));

%o };

%o A066537_seq(N) = {

%o   my(x='x+O('x^(N+3)));

%o   Vec(serlaplace(exp(serconvol(Ser(A096332_seq(N))*'x,exp(x)))));

%o };

%o A066537_seq(15) \\ _Gheorghe Coserea_, Aug 10 2017

%Y Cf. A005470, A096330, A096331, A096332 (connected), A100960, A266390, A266391.

%K nice,nonn

%O 0,3

%A Aart Blokhuis (aartb(AT)win.tue.nl), Jan 08 2002

%E More terms from Manuel Bodirsky (bodirsky(AT)informatik.hu-berlin.de), Sep 15 2003

%E Entry revised by _N. J. A. Sloane_, Jun 17 2006