A096332 Number of connected planar graphs on n labeled nodes.

1, 1, 4, 38, 727, 26013, 1597690, 149248656, 18919743219, 3005354096360, 569226803220234, 124594074249852576, 30861014504270954737, 8520443838646833231236, 2592150684565935977152860, 861079753184429687852978432, 310008316267496041749182487881

Offset: 1

Author

Steven Finch, Aug 02 2004

Keywords

• nonn
• hard

Examples

			There are 4 connected labeled planar graphs on 3 nodes:
1-2-3,
1-3-2,
2-1-3 and
1-2
|/
3
		

References

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

Links

• Gheorghe Coserea, Table of n, a(n) for n = 1..126
• 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.
• O. Gimenez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, arXiv:math/0501269 [math.CO], 2005.

Crossrefs

Cf. A066537, A096331, A266390, A266392, A267411.

Programs

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)));
};
A096332_seq(15) \\ Gheorghe Coserea, Aug 10 2017

Formula

This is generated by log(1+g(x)), where g(x) is the e.g.f. for labeled planar graphs, which may be computed from recurrences in Bodirsky et al. - Keith Briggs, Feb 04 2005

a(n) ~ c * n^(-7/2) * gamma^n * n!, where c = 0.00000410436110025...(A266392) and gamma = 27.2268777685...(A266390) (see Gimenez and Noy). - Gheorghe Coserea, Feb 24 2016

Extensions

More terms from Keith Briggs, Feb 04 2005

More terms from Alois P. Heinz, Dec 30 2015