A066537 Number of planar graphs on n labeled nodes.

1, 1, 2, 8, 64, 1023, 32071, 1823707, 163947848, 20402420291, 3209997749284, 604611323732576, 131861300077834966, 32577569614176693919, 8977083127683999891824, 2726955513946123452637877, 904755724004585279250537376, 325403988657293080813790670641

Offset

0,3

Comments

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.

References

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

Links

Keith M. Briggs and Gheorghe Coserea, Table of n, a(n) for n = 0..126, terms 0..42 from Keith M. Briggs.

M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, ICALP03 Eindhoven, LNCS 2719, Springer Verlag (2003), 1095 - 1107.

M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, Pages 377-386.

Keith M. Briggs, Combinatorial Graph Theory

O. Gimenez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, arXiv:math/0501269 [math.CO], 2005.

Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato, Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration, arXiv:1911.07465 [cs.DS], 2019.

A. Taraz, D. Osthus and H. J. Proemel, On random planar graphs, the number of planar graphs and their triangulations Journal of Combinatorial Theory, Series B, 88 (2003), 119-134.

Formula

Recurrence known, see Bodirsky et al.

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

Prog

(PARI)
Q(n, k) = { \\ c-nets with n-edges, k-vertices
  if (k < 2+(n+2)\3 || k > 2*n\3, return(0));
  sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k, i)*i*(i-1)/2*
  (binomial(2*n-2*k+2, k-i)*binomial(2*k-2, n-j) -
  4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));
};
A100960_ser(N) = {
my(x='x+O('x^(3*N+1)), t='t+O('t^(N+4)),
   q=t*x*Ser(vector(3*N+1, n, Polrev(vector(min(N+3, 2*n\3), k, Q(n, k)), 't))),
   d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),
   g2=intformal(t^2/2*((1+d)/(1+x)-1)));
   serlaplace(Ser(vector(N, n, subst(polcoeff(g2, n, 't), 'x, 't)))*'x);
};
A096331_seq(N) = Vec(subst(A100960_ser(N+2), 't, 1));
A096332_seq(N) = {
  my(x='x+O('x^(N+3)), b=x^2/2+serconvol(Ser(A096331_seq(N))*x^3, exp(x)));
  Vec(serlaplace(intformal(serreverse(x/exp(b'))/x)));
};
A066537_seq(N) = {
  my(x='x+O('x^(N+3)));
  Vec(serlaplace(exp(serconvol(Ser(A096332_seq(N))*'x, exp(x)))));
};
A066537_seq(15) \\ Gheorghe Coserea, Aug 10 2017

Crossrefs

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

Sequence in context: A153543 A153571 A086789 * A084280 A153534 A153563

Adjacent sequences: A066534 A066535 A066536 * A066538 A066539 A066540

Keyword

nice,nonn

Author

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

Extensions

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

Entry revised by N. J. A. Sloane, Jun 17 2006

Status

approved