A059525 Number of nonzero n X n binary arrays with all 1's connected.

0, 1, 13, 218, 11506, 2301877, 1732082741, 4872949974666, 51016818604894742, 1980555831431088025753, 284374318545830329487309785, 150730745416633777472365437495914, 294516896499779486414143877573183893666, 2119097214294718323017954923662829194285541981

Offset: 0

Author

David Radcliffe, Jan 21 2001

Keywords

• nonn
• hard

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

• Andrew Howroyd, Table of n, a(n) for n = 0..16
• 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

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

Programs

Mathematica

Table[Count[Subgraph[GridGraph[{n, n}], #] & /@ Subsets[Range[n^2], {1, Infinity}], ?ConnectedGraphQ], {n, 4}] (* _Eric W. Weisstein, May 01 2017 *)

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