login
A286186
Number of connected induced (non-null) subgraphs of the friendship graph with 2n+1 nodes.
15
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
Eric Weisstein's World of Mathematics, Dutch Windmill Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Friendship graph
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
KEYWORD
nonn,easy
AUTHOR
Giovanni Resta, May 04 2017
STATUS
approved