A059020 -id:A059020 - 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

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

Original entry on oeis.org

1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Main diagonal of A360873.
Cf. A262307, A183109.
Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A285765 (queen).

{1} ~ Join ~ Table[g = GraphData[{"Rook", {n,n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 2, 4}]
(* Second program: *)
(* b = A183109, T = A262307 *)
b[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
T[m_, n_] := T[m, n] = b[m, n] - Sum[T[i, j]*b[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
a[n_] := Sum[Binomial[n, i]*Binomial[n, j]*T[i, j], {i, 1, n}, {j, 1, n}];
Array[a, 12] (* Jean-François Alcover, Oct 11 2017, after Andrew Howroyd *)

G(N)={my(S=matrix(N,N), T=matrix(N,N), U=matrix(N,N));
\\ S is A183109, T is A262307, U is mxn variant of this sequence.
for(m=1,N,for(n=1,N,
S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
T[m,n]=S[m,n]-sum(i=1, m-1, sum(j=1, n-1, T[i,j]*S[m-i,n-j]*binomial(m-1,i-1)*binomial(n,j)));
U[m,n]=sum(i=1,m,sum(j=1,n,binomial(m,i)*binomial(n,j)*T[i,j])) ));U}
a(n)=G(n)[n,n]; \\ Andrew Howroyd, May 22 2017

a(n) = Sum_{i=1..n} Sum_{j=1..n} binomial(n,i)*binomial(n,j)*A262307(i,j). - Andrew Howroyd, May 22 2017

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 12 2017

Terms a(7) and beyond from Andrew Howroyd, May 22 2017

A286139 Number of connected induced (non-null) subgraphs of the n X n king graph.

Original entry on oeis.org

1, 15, 388, 37196, 14765089, 24076152503, 159850328891568, 4290837646252661680, 463376724731585422732393, 200665409586497566263900755703, 347694350828123116321061347501951972, 2406781070555276417850396576804205226358828, 66481859567653621586313146932097075651519991887257

Offset: 1

Giovanni Resta, May 03 2017

Andrew Howroyd, Table of n, a(n) for n = 1..16
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

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

Table[If[n<2, n, g = GraphData[{"King", {n, n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}]], {n, 4}]

a(10)-a(13) from Andrew Howroyd, May 20 2017

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

Original entry on oeis.org

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 213, 108, 15, 21, 275, 1049, 1049, 275, 21, 28, 681, 5034, 9349, 5034, 681, 28, 36, 1664, 23984, 80626, 80626, 23984, 1664, 36, 45, 4040, 114069, 692194, 1222363, 692194, 114069, 4040, 45

Offset: 1

Douglas Boffey, Nov 14 2013

This sequence is read in a table, thus:
    m ->
    1,  3,  6, 10, …
n   3, 13, 40, …
|   6, 40, …
v  10, …
    …
This sequence gives the number of closed, simple loops on a rectangular lattice of dots, where the edges of the loop can be horizontal or vertical.
This is also the number of solutions to an unclued slitherlink puzzle.
Main diagonal is A140517. - Joerg Arndt, Sep 01 2014
Equivalently, the number of cycles in the grid graph P_{m+1} X P_{n+1}. - Andrew Howroyd, Jun 12 2017

			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    213    1049      5034       23984       114069...
4  | 10  108   1049    9349     80626      692194      5948291...
5  | 15  275   5034   80626   1222363    18438929    279285399...
6  | 21  681  23984  692194  18438929   487150371  12947640143...
7  | 28 1664 114069 5948291 279285399 12947640143 603841648931...
... - _Andrew Howroyd_, Jun 12 2017
a(2,2) = 13, thus:
1)        2)        3)        4)        5)
+-+ +     + +-+     + + +     + + +     +-+ +
| |         | |                         | |
+-+ +     + +-+     +-+ +     + +-+     + + +
                    | |         | |     | |
+ + +     + + +     +-+ +     + +-+     +-+ +
6)        7)        8)        9)        10)
+ +-+     +-+-+     + + +     +-+ +     + +-+
  | |     |   |               | |         | |
+ + +     +-+-+     +-+-+     + +-+     +-+ +
  | |               |   |     |   |     |   |
+ +-+     + + +     +-+-+     +-+-+     +-+-+
11)       12)       13)
+-+-+     +-+-+     +-+-+
|   |     |   |     |   |
+-+ +     + +-+     + + +
  | |     | |       |   |
+ +-+     +-+ +     +-+-+

Douglas Boffey and Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..70 from Douglas Boffey)
Wikipedia, Slitherlink

Rows 2..10 are A059020, A288637, A339117, A339118, A339119, A339120, A339121, A358707, A358785.
Main diagonal is A140517.
Cf. A288518, A003763, A222202.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A231829(n, k):
    universe = tl.grid(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A231829(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Nov 24 2020

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

Original entry on oeis.org

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

Offset: 1

Giovanni Resta, May 04 2017

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Prism Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (6, -11, 4, 5, -2, -1).

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

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]

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).
a(n) = A002203(n) + 3*n*A000129(n) - 3*n + 1 (conjectured). - Eric W. Weisstein, May 08 2017
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

Terms a(18) and beyond from Andrew Howroyd, Aug 15 2017

A286183 Number of connected induced (non-null) subgraphs of the antiprism graph with 2n nodes.

Original entry on oeis.org

3, 15, 60, 207, 663, 2038, 6107, 17983, 52272, 150407, 429223, 1216490, 3427635, 9609327, 26821668, 74576703, 206650167, 570877918, 1572754187, 4322192287, 11851474968, 32430381815, 88576465735, 241511251922, 657457204323, 1787147867343, 4851349002252

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Antiprism Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

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

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

a(n) = 8*a(n-1) - 24*a(n-2) + 34*a(n-3) - 24*a(n-4) + 8*a(n-5) - a(n-6), for n > 6 (conjectured).
a(n) = A005248(n) - 2*n + 2*n*A001906(n) (conjectured). - Eric W. Weisstein, May 08 2017
G.f.: x*(3 - 9*x + 12*x^2 - 15*x^3 + 9*x^4 - 2*x^5) / ((1 - x)^2*(1 - 3*x + x^2)^2) (conjectured). - Colin Barker, May 30 2017

a(17)-a(27) from Andrew Howroyd, May 20 2017

A286184 Number of connected induced (non-null) subgraphs of the helm graph with 2n+1 nodes.

Original entry on oeis.org

6, 19, 56, 157, 430, 1171, 3204, 8857, 24794, 70303, 201712, 584677, 1708998, 5028715, 14873180, 44160817, 131499442, 392401207, 1172747208, 3508804477, 10506490526, 31477528579, 94344505396, 282848966857, 848161024650, 2543677767631, 7629355581344

Offset: 1

Giovanni Resta, May 04 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Andrew Howroyd, Combinatorial Proof of Formula
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

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

[3^n + (1+n)*2^n - n: n in [1..30]]; // Vincenzo Librandi, May 21 2017

a[n_] := Block[{g = Graph@ Flatten@ Table[{i <-> Mod[i, n] + 1, i <-> n + Mod[i, n] + 1, i <-> 2 n + 1}, {i, n}]}, -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[2 n + 1]}]]; Array[a, 8]
Table[3^n + (1 + n) 2^n - n, {n, 30}] (* Vincenzo Librandi, May 21 2017 *)
CoefficientList[Series[(6 - 35 x + 71 x^2 - 64 x^3 + 24 x^4) / ((1-3x)(1-2x)^2(1-x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, May 21 2017 *)
LinearRecurrence[{9, -31, 51, -40, 12}, {6, 19, 56, 157, 430}, 20] (* Eric W. Weisstein, May 28 2017 *)

a(n) = 3^n + (1 + n)*2^n - n.
a(n) = 9*a(n-1) - 31*a(n-2) + 51*a(n-3) - 40*a(n-4) + 12*a(n-5). - Eric W. Weisstein, May 28 2017
G.f.: x*(6 - 35*x + 71*x^2 - 64*x^3 + 24*x^4)/((1 - 3*x)*(1 - 2*x)^2*(1 - x)^2). - Vincenzo Librandi, May 21 2017
E.g.f.: exp(3*x) - x*exp(x) + exp(2*x)*(1 + 2*x) - 2. - Stefano Spezia, Aug 25 2022

a(17)-a(27) from Andrew Howroyd, May 21 2017

A286185 Number of connected induced (non-null) subgraphs of the Möbius ladder graph with 2n nodes.

Original entry on oeis.org

3, 15, 55, 173, 511, 1451, 4019, 10937, 29371, 78055, 205679, 538149, 1399607, 3621315, 9327723, 23931633, 61186163, 155949119, 396369831, 1004904733, 2541896559, 6416348251, 16165611043, 40657256617, 102090514731, 255968753175, 640899345631, 1602640560533

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Möbius Ladder
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

a[n_] := Block[{g = CirculantGraph[2 n, {1, n}]}, -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[2 n]}]]; Array[a, 8]

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).
a(n) = 1/4*((1-sqrt(2))^n*(4-3*sqrt(2)*n) + (1+sqrt(2))^n*(4+3*sqrt(2)*n)) - 1 - n (conjectured). - Eric W. Weisstein, May 08 2017
a(n) = Lucas(n, 2) + 3*n*Fibonacci(n, 2) - n - 1, where Lucas(n, 2) = A002203(n) and Fibonacci(n, 2) = A000129(n) (conjectured). - Eric W. Weisstein, May 08 2017
G.f. (subject to the above conjectures. In fact all three conjectures are equivalent): (3*x-3*x^2-2*x^3-4*x^4+3*x^5-x^6)/(1-3*x+x^2+x^3)^2. - Robert Israel, May 08 2017

a(17)-a(28) from Andrew Howroyd, May 20 2017

A286187 Number of connected induced (non-null) subgraphs of the web graph with 3n nodes.

Original entry on oeis.org

6, 33, 188, 985, 4990, 24645, 119712, 574225, 2727218, 12847821, 60115060, 279652793, 1294441894, 5965567125, 27387631368, 125308264225, 571591760602, 2600204421405, 11799376912220, 53424388364873, 241398575303374, 1088727972172389, 4901842528232304, 22034981672761649

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Eric Weisstein's World of Mathematics, Web Graph

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

{6, 33} ~Join~ Table[g = GraphData[{"Web", n}]; -1 + ParallelSum[Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[3 n]}], {n, 3, 6}]

Empirical g.f.: x*(6 - 39*x + 92*x^2 - 101*x^3 + 32*x^4 - 8*x^5 + 64*x^6 - 48*x^7) / ((1 - x)^2*(1 - 5*x + 2*x^2 + 4*x^3)^2). - Colin Barker, May 21 2017

a(12)-a(24) from Andrew Howroyd, May 20 2017

A286188 Number of connected induced (non-null) subgraphs of the gear graph with 2n+1 nodes.

Original entry on oeis.org

6, 26, 76, 218, 664, 2174, 7452, 26130, 92512, 328774, 1170052, 4166106, 14836488, 52839374, 188188396, 670240802, 2387095600, 8501764310, 30279479508, 107841961962, 384084839128, 1367938434910, 4871984975932, 17351831789874, 61799465313024

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Gear Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (6, -10, 4, 3, -2).

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

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

a(n) = 6*a(n-1) - 10*a(n-2) + 4*a(n-3) + 3*a(n-4) - 2*a(n-5), for n>5.
a(n) = A206776(n) + 4*n^2 - 2*n + 1. - Eric W. Weisstein, May 08 2017
G.f.: 2*x*(3 - 5*x - 10*x^2 - x^3 - 3*x^4) / ((1 - x)^3*(1 - 3*x - 2*x^2)). - Colin Barker, May 31 2017

a(16)-a(25) from 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

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A286139 Number of connected induced (non-null) subgraphs of the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A286183 Number of connected induced (non-null) subgraphs of the antiprism graph with 2n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A286184 Number of connected induced (non-null) subgraphs of the helm graph with 2n+1 nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A286185 Number of connected induced (non-null) subgraphs of the Möbius ladder graph with 2n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs