A059021 -id:A059021 - cp's OEIS frontend

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

David Radcliffe, Jan 21 2001

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

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

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

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

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

A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

Original entry on oeis.org

0, 3, 13, 40, 108, 275, 681, 1664, 4040, 9779, 23637, 57096, 137876, 332899, 803729, 1940416, 4684624, 11309731, 27304157, 65918120, 159140476, 384199155, 927538873, 2239276992, 5406092952, 13051462995, 31509019045, 76069501192, 183648021540, 443365544387

Offset: 0

John W. Layman, Dec 14 2000

In other words, the number of connected (non-null) induced subgraphs in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, May 02 2017

Also, the number of cycles in the grid graph P_3 X P_{n+1}. - Andrew Howroyd, Jun 12 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Induced Subgraph.
Eric Weisstein's World of Mathematics, Ladder Graph.
Index entries for linear recurrences with constant coefficients, signature (4,-4,0,1).

Row 2 of A287151 and row 2 of A231829.
See also A059021, A059524.
Cf. A000129. - Jaume Oliver Lafont, Sep 28 2009
Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.

I:=[0, 3, 13, 40];[n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4):n in [1..30]]; // Marius A. Burtea, Aug 25 2019

Join[{0},LinearRecurrence[{4, -4, 0, 1}, {3, 13, 40, 108}, 20]] (* Eric W. Weisstein, May 02 2017 *) (* adapted by Vincenzo Librandi, May 09 2017 *)
Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* Eric W. Weisstein, May 02 2017 *)

a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.
From Jaume Oliver Lafont, Nov 23 2008: (Start)
a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)
G.f.: x*(3+x)/((1-2*x-x^2)*(1-x)^2). - Jaume Oliver Lafont, Sep 28 2009
Empirical observations (from Superseeker):
(1) if b(n) = a(n) + n then {b(n)} is A048777;
(2) if b(n) = a(n+3) - 3*a(n+2) - 3*a(n+1) + a(n) then {b(n)} is A052542;
(3) if b(n) = a(n+2) - 2*a(n+1) + a(n) then {b(n)} is A001333.
4*a(n) = A002203(n+3) - 8*n - 14. - Eric W. Weisstein, May 02 2017
a(n) = 3*A048776(n-1) + A048776(n-2). - R. J. Mathar, May 12 2019
E.g.f.: (1/2)*exp(x)*(-7-4*x+7*cosh(sqrt(2)*x)+5*sqrt(2)*sinh(sqrt(2)*x)). - Stefano Spezia, Aug 25 2019

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

Original entry on oeis.org

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 218, 108, 15, 21, 275, 1126, 1126, 275, 21, 28, 681, 5726, 11506, 5726, 681, 28, 36, 1664, 28992, 116166, 116166, 28992, 1664, 36, 45, 4040, 146642, 1168586, 2301877, 1168586, 146642, 4040, 45, 55, 9779, 741556, 11749134, 45280509, 45280509, 11749134, 741556, 9779, 55

Offset: 1

Andrew Howroyd, May 20 2017

Also the number of connected induced (non-null) subgraphs of the grid graph P_m X P_n.

All rows (or columns) are linear recurrences with constant coefficients and the order of the recurrence of row m is at most 1 + A378941(m+1). At least for columns up to 7, this bound gives the actual order of the recurrence. The second differences of any column give those arrays that touch the top and bottom boundaries and have a recurrence order of 2 less since a finite state machine to enumerate these does not require states for empty rows. The number of states required is also considered in A140662 but does not take symmetry into account. - Andrew Howroyd, Dec 18 2024

			Table starts:
====================================================================
m\n|  1    2      3        4         5           6             7
---|----------------------------------------------------------------
1  |  1    3      6       10        15          21            28 ...
2  |  3   13     40      108       275         681          1664 ...
3  |  6   40    218     1126      5726       28992        146642 ...
4  | 10  108   1126    11506    116166     1168586      11749134 ...
5  | 15  275   5726   116166   2301877    45280509     889477656 ...
6  | 21  681  28992  1168586  45280509  1732082741   66037462454 ...
7  | 28 1664 146642 11749134 889477656 66037462454 4872949974666 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Induced Subgraph

Rows 2..5 are A059020, A059021, A059524, A378940.
Main diagonal is A059525.
Cf. A116469, A140662, A286139, A286189, A292357, A378941.

A163029 Number of n X 3 binary arrays with all 1's connected and a path of 1's from top row to bottom row.

Original entry on oeis.org

6, 28, 144, 730, 3692, 18666, 94384, 477264, 2413346, 12203374, 61707810, 312032874, 1577831334, 7978491800, 40344192708, 204005208738, 1031576601204, 5216289773894, 26376789637884, 133377373911160, 674438554337506

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

R. H. Hardin, Table of n, a(n) for n = 1..100
Chaim Goodman-Strauss, Notes on the number of m × n binary arrays with all 1’s connected and a path of 1’s from top row to bottom row (May 21 2020)
Chaim Goodman-Strauss, Mma notebook to accompany the above document

Cf. A001333 ((n-1) X 2 arrays), A059021 (no path required).

Cf. also A163030, A163031, A163032, A163033, A163034, A163035, A163036.

a(n) = 7*a(n-1) - 11*a(n-2) + 6*a(n-3) + a(n-4) - 7*a(n-5) + a(n-6). [Conjectured by R. J. Mathar, Aug 11 2009]
Proof from Peter Kagey, May 08 2019: Scanning from top to bottom, there are 6 possible intermediate states that the bottom row can be in. The transitions between these states define a 6 X 6 transition matrix whose characteristic polynomial agrees with the characteristic polynomial of the above recurrence. QED
For an alternative proof see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

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

Original entry on oeis.org

0, 10, 108, 1126, 11506, 116166, 1168586, 11749134, 118127408, 1187692422, 11941503498, 120064335342, 1207171430452, 12137349489598, 122033415224922, 1226969238084836, 12336404001299200, 124034783402890620, 1247091736942594618, 12538723071673581562

Offset: 0

David Radcliffe, Jan 21 2001

nonn

Old name was "Number of 4 X n checkerboards in which the set of red squares is edge connected".

The number of connected (non-null) induced subgraphs in the grid graph P_4 X P_n. - Andrew Howroyd, May 20 2017

			a(1) = 10 because there are 4 positions to place a single 1, 3 ways to place a pair of adjacent 1's, 2 ways to place a triple of connected 1's, and 1 way for the all-1's array: 4+3+2+1=10. - _R. J. Mathar_, Mar 13 2023

Andrew Howroyd, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (17,-90,230,-272,-75,623,-632,65,255,-198,162,-96,11,1).

Row 4 of A287151.

Cf. A059020, A059021.

Empirical g.f.: 2*x*(1 + x)*(5 - 36*x + 131*x^2 - 239*x^3 + 131*x^4 + 94*x^5 - 157*x^6 + 61*x^7 - 73*x^8 + 18*x^9 + x^10) / ((1 - x)^2*(1 - 15*x + 59*x^2 - 97*x^3 + 19*x^4 + 210*x^5 - 222*x^6 - 22*x^7 + 113*x^8 - 7*x^9 + 71*x^10 - 13*x^11 - x^12)). - Colin Barker, Oct 11 2017

The recurrence is correct. See A287151. - Andrew Howroyd, Dec 18 2024

Clearer name from R. H. Hardin, Jul 06 2009

a(16) corrected by Andrew Howroyd, May 20 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A163029 Number of n X 3 binary arrays with all 1's connected and a path of 1's from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions