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

3, 15, 54, 174, 537, 1629, 4908, 14748, 44271, 132843, 398562, 1195722, 3587205, 10761657, 32285016, 96855096, 290565339, 871696071, 2615088270, 7845264870, 23535794673, 70607384085, 211822152324, 635466457044, 1906399371207, 5719198113699, 17157594341178

Offset

1,1

Comments

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

Links

Table of n, a(n) for n=1..27.

Eric Weisstein's World of Mathematics, Connected Graph.

Eric Weisstein's World of Mathematics, Dorogovtsev-Goltsev-Mendes Graph.

Eric Weisstein's World of Mathematics, Graph Cycle.

Eric Weisstein's World of Mathematics, King Graph.

Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph.

Index entries for linear recurrences with constant coefficients, signature (5, -7, 3).

Formula

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

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

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

Mathematica

Table[3/4 (3^(n + 1) - 2 n - 3), {n, 20}]
LinearRecurrence[{5, -7, 3}, {3, 15, 54}, 40]
CoefficientList[Series[-3/((-1 + x)^2 (-1 + 3 x)), {x, 0, 20}], x]

Crossrefs

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

Sequence in context: A332375 A298178 A147618 * A286986 A261565 A085480

Adjacent sequences: A290761 A290762 A290763 * A290765 A290766 A290767

Keyword

nonn,easy

Author

Eric W. Weisstein, Aug 10 2017

Status

approved