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

Author

Stefano Spezia, May 06 2020

Keywords

• nonn
• easy

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.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A000217, A079566, A085930, A328180.

Programs

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]];

Mathematica

Join[{0, 0, 0, 0}, Table[(n^2+3n-22)/2, {n, 4, 54}]]

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)

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