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