

A296515


Number of edges in a maximal planar graph with n vertices.


3



0, 0, 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

{a(n)} is a monotonic increasing sequence because a maximal planar graph of order n can be generated on n + 1 nodes. Therefore a(n) <= a(n + 1).
Maximal planar graphs of order n > 5 are not unique.
E(G_2n) = (2n  1) + 2*Sum_{k=0..(floor(log_2(n  1)))} floor((n  1)/2^k) where E(G_2n) is the size of a minimal planar graph G of order 2n.
Number of edges of a maximal 3degenerate graph of order n (this class includes 3trees). The intersection of this class and maximal planar graphs is the Apollonian networks (planar 3trees); neither class contains the other.  Allan Bickle, Nov 14 2021
a(n) is the number of blocks to dig (in a staircase fashion) to get out of a hole of depth n in Minecraft.  Max R Anderson, Oct 19 2023


LINKS



FORMULA

a(n) = floor(6/2^n) + 3n  6 (see comments section of A008486).
E.g.f.: 6 + x*(x + 6)/2 + 3*exp(x)*(x  2).  Stefano Spezia, Feb 13 2023


MATHEMATICA

CoefficientList[Series[(x^2 (1 + x + x^2))/(x  1)^2, {x, 0, 60}], x] (* or *) LinearRecurrence[{2, 1}, {0, 0, 1, 3}, 60] (* Robert G. Wilson v, Mar 04 2018 *)


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



