A286186 Number of connected induced (non-null) subgraphs of the friendship graph with 2n+1 nodes.

7, 22, 73, 268, 1039, 4114, 16405, 65560, 262171, 1048606, 4194337, 16777252, 67108903, 268435498, 1073741869, 4294967344, 17179869235, 68719476790, 274877907001, 1099511627836, 4398046511167, 17592186044482, 70368744177733, 281474976710728, 1125899906842699

Offset

1,1

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Dutch Windmill Graph

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

Wikipedia, Friendship graph

Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Formula

a(n) = 4^n + 3*n.

From Colin Barker, May 21 2017: (Start)

G.f.: x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).

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

E.g.f.: exp(x)*(exp(3*x) + 3*x) - 1. - Stefano Spezia, Aug 25 2022

Mathematica

Table[4^n + 3 n, {n, 30}]
LinearRecurrence[{6, -9, 4}, {7, 22, 73}, 40] (* Harvey P. Dale, May 25 2019 *)

Prog

(PARI) Vec(x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 21 2017

Crossrefs

Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

Sequence in context: A101289 A085287 A278767 * A282035 A302273 A151822

Adjacent sequences: A286183 A286184 A286185 * A286187 A286188 A286189

Keyword

nonn,easy

Author

Giovanni Resta, May 04 2017

Status

approved