login
Number of (non-null) connected induced subgraphs in the 2 X n king graph.
2

%I #15 Dec 30 2023 13:17:36

%S 3,15,54,174,537,1629,4908,14748,44271,132843,398562,1195722,3587205,

%T 10761657,32285016,96855096,290565339,871696071,2615088270,7845264870,

%U 23535794673,70607384085,211822152324,635466457044,1906399371207,5719198113699,17157594341178

%N Number of (non-null) connected induced subgraphs in the 2 X n king graph.

%C a(n) is also the number of 4-cycles in the (n+1)-Dorogovtsev-Goltsev-Mendes graph (using the indexing convention that the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - _Eric W. Weisstein_, Dec 06 2023

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html">Dorogovtsev-Goltsev-Mendes Graph</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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>.

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

%F a(n) = 3/4*(3^(n + 1) - 2*n - 3).

%F a(n) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3).

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

%t Table[3/4 (3^(n + 1) - 2 n - 3), {n, 20}]

%t LinearRecurrence[{5, -7, 3}, {3, 15, 54}, 40]

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

%Y Cf. A003462(n) (3-cycles), A367967(n) (5-cycles), A367968(n) (6-cycles).

%K nonn,easy

%O 1,1

%A _Eric W. Weisstein_, Aug 10 2017