|
|
A286182
|
|
Number of connected induced (non-null) subgraphs of the prism graph with 2n nodes.
|
|
17
|
|
|
3, 13, 51, 167, 503, 1441, 4007, 10923, 29355, 78037, 205659, 538127, 1399583, 3621289, 9327695, 23931603, 61186131, 155949085, 396369795, 1004904695, 2541896519, 6416348209, 16165610999, 40657256571, 102090514683, 255968753125, 640899345579, 1602640560479
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Cases n=1 and n=2 correspond to degenerate prism graphs, but they fit the same (conjectured) linear recurrence as the other terms.
|
|
LINKS
|
|
|
FORMULA
|
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).
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
|
|
MATHEMATICA
|
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]
|
|
CROSSREFS
|
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).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|