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,1

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

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

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

Prog

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

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

Sequence in context: A272562 A176883 A274599 * A027044 A057571 A238055

Adjacent sequences: A286181 A286182 A286183 * A286185 A286186 A286187

Keyword

nonn,easy

Author

Giovanni Resta, May 04 2017

Extensions

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

Status

approved