login
A059525
Number of nonzero n X n binary arrays with all 1's connected.
23
0, 1, 13, 218, 11506, 2301877, 1732082741, 4872949974666, 51016818604894742, 1980555831431088025753, 284374318545830329487309785, 150730745416633777472365437495914, 294516896499779486414143877573183893666, 2119097214294718323017954923662829194285541981
OFFSET
0,3
COMMENTS
Old name was: "Number of n X n checkerboards in which the set of red squares is edge connected".
Also the number of connected induced (non-null) subgraphs of the n X n grid graph P_n x P_n. - Eric W. Weisstein, May 01 2017
LINKS
Stijn Cambie, Jan Goedgebeur, and Jorik Jooken, The maximum number of connected sets in regular graphs, arXiv:2311.00075 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Induced Subgraph
MATHEMATICA
Table[Count[Subgraph[GridGraph[{n, n}], #] & /@ Subsets[Range[n^2], {1, Infinity}], _?ConnectedGraphQ], {n, 4}] (* Eric W. Weisstein, May 01 2017 *)
CROSSREFS
Main diagonal of A287151.
Cf. A059021, A020873 (wheel), A059020 (ladder), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).
Sequence in context: A218475 A294982 A320627 * A086147 A329073 A015253
KEYWORD
nonn,hard
AUTHOR
David Radcliffe, Jan 21 2001
EXTENSIONS
One more term from John W. Layman, Jan 25 2001
More terms from R. H. Hardin, Feb 28 2002
Clearer name from R. H. Hardin, Jul 06 2009
a(8)-a(9) from Giovanni Resta, May 03 2017
a(10)-a(13) from Andrew Howroyd, May 20 2017
STATUS
approved