A059525 -id:A059525 - cp's OEIS frontend

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

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

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

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

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

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.

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

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

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs