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

0, 0, 0, 0, 0, 6, 24, 41, 60, 84, 112, 144, 180, 220, 264, 312, 364, 420, 480, 544, 612, 684, 760, 840, 924, 1012, 1104, 1200, 1300, 1404, 1512, 1624, 1740, 1860, 1984, 2112, 2244, 2380, 2520, 2664, 2812, 2964, 3120, 3280, 3444, 3612, 3784, 3960, 4140, 4324, 4512

Offset: 0

Author

Stefano Spezia, Oct 06 2019

Keywords

• nonn
• easy

Comments

All the terms are even numbers except for a(7) = 41 which is also the only prime.

For n >= 5, also the number of 5-cycles in the (n-2)-dipyramidal graph. - Eric W. Weisstein, Dec 07 2023

Links

• Stefano Spezia, Table of n, a(n) for n = 0..10000
• Debarun Ghosh, Ervin Győri, Oliver Janzer, Addisu Paulos, Nika Salia, and Oscar Zamora, The maximum number of induced C_5's in a planar graph, arXiv:2004.01162 [math.CO], 2020.
• Ervin Győri, Addisu Paulos, Nika Salia, Casey Tompkins, and Oscar Zamora, The Maximum Number of Pentagons in a Planar Graph, arXiv:1909.13532 [math.CO], 2019.
• 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.
• Eric Weisstein's World of Mathematics, Dipyramidal Graph.
• Eric Weisstein's World of Mathematics, Graph Cycle.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A005843, A046092, A106232, A185721.

Programs

Magma

I:=[0, 0, 0, 0, 0, 6, 24, 41, 60, 84, 112]; [n le 11 select I[n] else 3*Self(n-1)-3*Self(n-2)+Self(n-3): n in [1..51]];

Magma

R:=PowerSeriesRing(Integers(),51); [0,0,0,0,0] cat Coefficients(R!(x^5*(-6-6*x+13*x^2-3*x^3-3*x^4+x^5)/(-1+x)^3)); // Marius A. Burtea, Oct 16 2019

Maple

gf := (1/5040)*x^7-(1/20)*x^5-(1/6)*x^4+2*exp(x)*x^2-8*exp(x)*x-4*x+12*exp(x)-12; ser := series(gf, x, 51); seq(factorial(n)*coeff(ser, x, n), n = 0..50)

Mathematica

Join[{0,0,0,0,0,6,24,41},Table[2n^2-10n+12,{n,8,50}]]
LinearRecurrence[{3,-3,1},{0,0,0,0,0,6,24,41,60,84,112},60] (* Harvey P. Dale, Jan 10 2022 *)

PARI

concat([0, 0, 0, 0, 0], Vec(x^5*(-6-6*x+13*x^2-3*x^3-3*x^4+x^5)/(-1+x)^3+O(x^51)))

Formula

O.g.f.: x^5*(-6 - 6*x + 13*x^2 - 3*x^3 - 3*x^4 + x^5)/(-1 + x)^3.

E.g.f.: x^7/5040 - x^5/20 - x^4/6 + 2*exp(x)*x^2 - 8*exp(x)*x - 4*x + 12*exp(x) - 12.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 10.

a(n) = 0 for n < 5, a(5) = 6, a(6) = 24, a(7) = 41, a(n) = 2*n^2 - 10*n + 12 for n > 7 (see Theorem 1 in Győri et al.).

a(n) = A046092(n-3) for n > 7.

a(n) = A106232(n-2) for n > 7.