A096330 -id:A096330 - cp's OEIS frontend

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

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

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.

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

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.

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

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

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

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

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

A343871 Number of labeled 3-connected planar graphs with n edges.

Original entry on oeis.org

1, 0, 15, 70, 432, 4320, 30855, 294840, 2883240, 28175952, 310690800, 3458941920, 40459730640, 499638948480, 6324655705200, 83653192972800, 1145266802114400, 16145338385736000, 235579813593453000, 3535776409508703360, 54571687068401395200, 866268656574795936000

Offset: 6

Andrew Howroyd, May 05 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 6..200
M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, pp. 377-386.

Cf. A000287, A002840 (unlabeled case), A096330, A290326, A291841, A338414.

Q(n,k) = { \\ c-nets with n-edges, k-vertices (see A290326)
  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))));
};
a(n)={sum(k=2+(n+2)\3, 2*n\3, k!*Q(n,k))/(4*n)} \\ Andrew Howroyd, May 05 2021

a(n) = Sum_{k=2+floor((n+2)/3)..floor(2*n/3)} k!*A290326(n-k+1, k-1)/(4*n).

cp's OEIS Frontend

A066537 Number of planar graphs on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions