login
Number of 4-cycles in the n X n king graph.
4

%I #22 Aug 15 2022 20:27:08

%S 0,3,29,79,153,251,373,519,689,883,1101,1343,1609,1899,2213,2551,2913,

%T 3299,3709,4143,4601,5083,5589,6119,6673,7251,7853,8479,9129,9803,

%U 10501,11223,11969,12739,13533,14351,15193,16059,16949,17863

%N Number of 4-cycles in the n X n king graph.

%H Colin Barker, <a href="/A288918/b288918.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

%F a(n) = 12*n^2 - 34*n + 23 for n > 1. - _Andrew Howroyd_, Jun 19 2017

%F From _Colin Barker_, Mar 11 2019: (Start)

%F G.f.: x^2*(3 + 20*x + x^2) / (1 - x)^3.

%F a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 4. (End)

%F E.g.f.: exp(x)*(23 - 22*x + 12*x^2) - 23 - x. - _Stefano Spezia_, Aug 14 2022

%t Table[If[n == 1, 0, 23 - 34 n + 12 n^2], {n, 20}]

%t Join[{0}, LinearRecurrence[{3, -3, 1}, {1, 3, 29}, {2, 20}]]

%t CoefficientList[Series[(-3 x - 20 x^2 - x^3)/(-1 + x)^3, {x, 0, 20}],x]

%o (PARI) a(n)=if(n, 12*n^2-10*n+1, 0) \\ _Charles R Greathouse IV_, Jun 19 2017

%o (PARI) concat(0, Vec(x^2*(3 + 20*x + x^2) / (1 - x)^3 + O(x^40))) \\ _Colin Barker_, Mar 11 2019

%Y Cf. A016742 (3-cycles), A288919 (5-cycles), A288920 (6-cycles).

%K nonn,easy

%O 1,2

%A _Eric W. Weisstein_, Jun 19 2017