|
|
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 3-degenerate graph of order n (this class includes 3-trees). The intersection of this class and maximal planar graphs is the Apollonian networks (planar 3-trees); 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
|
|
|
|