|
%I #33 Sep 08 2022 08:46:25
%S 0,0,0,0,3,9,16,24,33,43,54,66,79,93,108,124,141,159,178,198,219,241,
%T 264,288,313,339,366,394,423,453,484,516,549,583,618,654,691,729,768,
%U 808,849,891,934,978,1023,1069,1116,1164,1213,1263,1314,1366,1419,1473,1528
%N a(n) is the maximum number of 4-cycles possible in an n-vertex planar graph.
%C For n > 1, the parity changes every two terms like in A000217 for n > 0.
%H Debarun Ghosh, Ervin Győri, Oliver Janzer, Addisu Paulos, Nika Salia, Oscar Zamora, <a href="https://arxiv.org/abs/2004.01162">The maximum number of induced C_5's in a planar graph</a>, arXiv:2004.01162 [math.CO], 2020.
%H S. L. Hakimi and E. F. Schmeichel, <a href="https://doi.org/10.1002/jgt.3190030108">On the number of cycles of length k in a maximal planar graph</a>, J. Graph Theory 3 (1979): 69-86.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F O.g.f.: x^4*(3 - 2*x^2)/(1 - x)^3.
%F E.g.f.: 11 + 9*x + 3*x^2 + x^3/3 + exp(x)*(x^2 + 4*x - 22)/2.
%F a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 6.
%F a(n) = (n^2 + 3*n - 22)/2 for n > 3 and 0 otherwise (see Theorem 2 in Hakimi and Schmeichel).
%F a(n) = a(n-1) + n + 1 for n > 4.
%F a(n) = A000217(n) + n - 11 for n > 3.
%F a(n) = A085930(12, n-3) for 3 < n < 16. - _Michel Marcus_, Jun 01 2020
%t Join[{0, 0, 0, 0}, Table[(n^2+3n-22)/2, {n, 4, 54}]]
%o (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]];
%o (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)))
%o (Sage) (x^4*(3 - 2*x^2)/(1 - x)^3).series(x, 55).coefficients(x, sparse=False)
%Y Cf. A000217, A079566, A085930, A328180.
%K nonn,easy
%O 0,5
%A _Stefano Spezia_, May 06 2020
|
