A286182 - OEIS

%I #26 Nov 28 2024 09:14:13

%S 3,13,51,167,503,1441,4007,10923,29355,78037,205659,538127,1399583,

%T 3621289,9327695,23931603,61186131,155949085,396369795,1004904695,

%U 2541896519,6416348209,16165610999,40657256571,102090514683,255968753125,640899345579,1602640560479

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

%C Cases n=1 and n=2 correspond to degenerate prism graphs, but they fit the same (conjectured) linear recurrence as the other terms.

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism 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_06">Index entries for linear recurrences with constant coefficients</a>, signature (6, -11, 4, 5, -2, -1).

%F a(n) = 6*a(n-1) - 11*a(n-2) + 4*a(n-3) + 5*a(n-4) - 2*a(n-5) - a(n-6), for n > 6 (conjectured).

%F a(n) = A002203(n) + 3*n*A000129(n) - 3*n + 1 (conjectured). - _Eric W. Weisstein_, May 08 2017

%F G.f.: x*(3 - 5*x + 6*x^2 - 8*x^3 - 5*x^4 - 3*x^5) / ((1 - x)^2*(1 - 2*x - x^2)^2) (conjectured). - _Colin Barker_, May 31 2017

%t a[n_] := Block[{g = Graph@ Flatten@ Table[{i <-> Mod[i,n] + 1, n+i <-> Mod[i,n] + n+1, i <-> i+n}, {i, n}]}, -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@Range[2 n]}]]; Array[a, 8]

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

%K nonn

%O 1,1

%A _Giovanni Resta_, May 04 2017

%E Terms a(18) and beyond from _Andrew Howroyd_, Aug 15 2017