login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066537 Number of planar graphs on n labeled nodes. 8
1, 1, 2, 8, 64, 1023, 32071, 1823707, 163947848, 20402420291, 3209997749284, 604611323732576, 131861300077834966, 32577569614176693919, 8977083127683999891824, 2726955513946123452637877, 904755724004585279250537376, 325403988657293080813790670641 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 21 14:54 EDT 2022. Contains 353921 sequences. (Running on oeis4.)