A334563 a(n) is the maximum number of 4-cycles possible in an n-vertex planar graph.

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

Table of n, a(n) for n=0..54.

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.

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

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

Cf. A000217, A079566, A085930, A328180.

Sequence in context: A020967 A253547 A290371 * A109340 A339918 A354258

Adjacent sequences: A334560 A334561 A334562 * A334564 A334565 A334566

Keyword

nonn,easy

Author

Stefano Spezia, May 06 2020

Status

approved