A286184 - OEIS

%I #23 Aug 25 2022 17:31:50

%S 6,19,56,157,430,1171,3204,8857,24794,70303,201712,584677,1708998,

%T 5028715,14873180,44160817,131499442,392401207,1172747208,3508804477,

%U 10506490526,31477528579,94344505396,282848966857,848161024650,2543677767631,7629355581344

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

%H Andrew Howroyd, <a href="/A286184/b286184.txt">Table of n, a(n) for n = 1..200</a>

%H Andrew Howroyd, <a href="/A286184/a286184.txt">Combinatorial Proof of Formula</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HelmGraph.html">Helm Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (9,-31,51,-40,12).

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

%F 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

%F 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

%F E.g.f.: exp(3*x) - x*exp(x) + exp(2*x)*(1 + 2*x) - 2. - _Stefano Spezia_, Aug 25 2022

%t 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]

%t Table[3^n + (1 + n) 2^n - n, {n, 30}] (* _Vincenzo Librandi_, May 21 2017 *)

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

%t LinearRecurrence[{9, -31, 51, -40, 12}, {6, 19, 56, 157, 430}, 20] (* _Eric W. Weisstein_, May 28 2017 *)

%o (Magma) [3^n + (1+n)*2^n - n: n in [1..30]]; // _Vincenzo Librandi_, May 21 2017

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

%K nonn,easy

%O 1,1

%A _Giovanni Resta_, May 04 2017

%E a(17)-a(27) from _Andrew Howroyd_, May 21 2017