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

Author

Giovanni Resta, May 04 2017

Keywords

• nonn
• easy

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).

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).

Programs

Mathematica

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

PARI

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

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