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

6, 19, 56, 157, 430, 1171, 3204, 8857, 24794, 70303, 201712, 584677, 1708998, 5028715, 14873180, 44160817, 131499442, 392401207, 1172747208, 3508804477, 10506490526, 31477528579, 94344505396, 282848966857, 848161024650, 2543677767631, 7629355581344

Offset: 1

Author

Giovanni Resta, May 04 2017

Keywords

• nonn
• easy

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Andrew Howroyd, Combinatorial Proof of Formula
• Eric Weisstein's World of Mathematics, Helm Graph
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
• Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

Crossrefs

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

Programs

Magma

[3^n + (1+n)*2^n - n: n in [1..30]]; // Vincenzo Librandi, May 21 2017

Mathematica

a[n_] := Block[{g = Graph@ Flatten@ Table[{i <-> Mod[i, n] + 1, i <-> n + Mod[i, n] + 1, i <-> 2 n + 1}, {i, n}]}, -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[2 n + 1]}]]; Array[a, 8]
Table[3^n + (1 + n) 2^n - n, {n, 30}] (* Vincenzo Librandi, May 21 2017 *)
CoefficientList[Series[(6 - 35 x + 71 x^2 - 64 x^3 + 24 x^4) / ((1-3x)(1-2x)^2(1-x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, May 21 2017 *)
LinearRecurrence[{9, -31, 51, -40, 12}, {6, 19, 56, 157, 430}, 20] (* Eric W. Weisstein, May 28 2017 *)

Formula

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

a(n) = 9*a(n-1) - 31*a(n-2) + 51*a(n-3) - 40*a(n-4) + 12*a(n-5). - Eric W. Weisstein, May 28 2017

G.f.: x*(6 - 35*x + 71*x^2 - 64*x^3 + 24*x^4)/((1 - 3*x)*(1 - 2*x)^2*(1 - x)^2). - Vincenzo Librandi, May 21 2017

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

Extensions

a(17)-a(27) from Andrew Howroyd, May 21 2017