login
A334563
a(n) is the maximum number of 4-cycles possible in an n-vertex planar graph.
1
0, 0, 0, 0, 3, 9, 16, 24, 33, 43, 54, 66, 79, 93, 108, 124, 141, 159, 178, 198, 219, 241, 264, 288, 313, 339, 366, 394, 423, 453, 484, 516, 549, 583, 618, 654, 691, 729, 768, 808, 849, 891, 934, 978, 1023, 1069, 1116, 1164, 1213, 1263, 1314, 1366, 1419, 1473, 1528
OFFSET
0,5
COMMENTS
For n > 1, the parity changes every two terms like in A000217 for n > 0.
LINKS
Debarun Ghosh, Ervin Győri, Oliver Janzer, Addisu Paulos, Nika Salia, Oscar Zamora, The maximum number of induced C_5's in a planar graph, arXiv:2004.01162 [math.CO], 2020.
S. L. Hakimi and E. F. Schmeichel, On the number of cycles of length k in a maximal planar graph, J. Graph Theory 3 (1979): 69-86.
FORMULA
O.g.f.: x^4*(3 - 2*x^2)/(1 - x)^3.
E.g.f.: 11 + 9*x + 3*x^2 + x^3/3 + exp(x)*(x^2 + 4*x - 22)/2.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 6.
a(n) = (n^2 + 3*n - 22)/2 for n > 3 and 0 otherwise (see Theorem 2 in Hakimi and Schmeichel).
a(n) = a(n-1) + n + 1 for n > 4.
a(n) = A000217(n) + n - 11 for n > 3.
a(n) = A085930(12, n-3) for 3 < n < 16. - Michel Marcus, Jun 01 2020
MATHEMATICA
Join[{0, 0, 0, 0}, Table[(n^2+3n-22)/2, {n, 4, 54}]]
PROG
(Magma) I:=[0, 0, 0, 0, 3, 9, 16]; [n le 7 select I[n] else 3*Self(n-1)-3*Self(n-2)+Self(n-3): n in [1..55]];
(PARI) my(x='x + O('x^55)); concat([0, 0, 0, 0], Vec(serlaplace(11 + 9*x + 3*x^2 + x^3/3 + exp(x)*(x^2 + 4*x - 22)/2)))
(Sage) (x^4*(3 - 2*x^2)/(1 - x)^3).series(x, 55).coefficients(x, sparse=False)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Stefano Spezia, May 06 2020
STATUS
approved