A059020 -id:A059020 - cp's OEIS frontend

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

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.

A285765 Number of connected induced (non-null) subgraphs of the n X n queen graph.

Original entry on oeis.org

1, 15, 495, 64815, 33478163, 68694593248

Offset: 1

Giovanni Resta, May 04 2017

Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

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

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

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

Original entry on oeis.org

7, 22, 73, 268, 1039, 4114, 16405, 65560, 262171, 1048606, 4194337, 16777252, 67108903, 268435498, 1073741869, 4294967344, 17179869235, 68719476790, 274877907001, 1099511627836, 4398046511167, 17592186044482, 70368744177733, 281474976710728, 1125899906842699

Offset: 1

Giovanni Resta, May 04 2017

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Dutch Windmill Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Friendship graph
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

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

Table[4^n + 3 n, {n, 30}]
LinearRecurrence[{6,-9,4},{7,22,73},40] (* Harvey P. Dale, May 25 2019 *)

Vec(x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 21 2017

a(n) = 4^n + 3*n.
From Colin Barker, May 21 2017: (Start)
G.f.: x*(7 - 20*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3. (End)
E.g.f.: exp(x)*(exp(3*x) + 3*x) - 1. - Stefano Spezia, Aug 25 2022

A059021 Number of 3 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, 6, 40, 218, 1126, 5726, 28992, 146642, 741556, 3749816, 18961450, 95880894, 484833212, 2451616864, 12396892316, 62686360476, 316981037374, 1602852315476, 8105013367472, 40983964057352, 207240288658392

Offset: 0

John W. Layman, Dec 14 2000

Number of nonzero 3 X n binary arrays with all 1's connected. Equivalently, the number of connected (non-null) induced subgraphs in the grid graph P_3 X P_n. - Andrew Howroyd, May 20 2017

Colin Barker, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (9,-26,35,-22,-3,16,-9,1).

Row 3 of A287151.

See A059020 for the 2 X n case and A059524 for the 4 X n case.

Table[-7/4 - 3 n/2 - RootSum[-1 + 7 # - #^2 - 6 #^3 + 11 #^4 - 7 #^5 + #^6 &, -60219359 #^n + 44281168 #^(1 + n) + 293383797 #^(2 + n) - 152425571 #^(3 + n) - 51762232 #^(4 + n) + 12785939 #^(5 + n) &]/2083234808, {n, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
LinearRecurrence[{9, -26, 35, -22, -3, 16, -9, 1}, {6, 40, 218, 1126, 5726, 28992, 146642, 741556}, 20] (* Eric W. Weisstein, Aug 09 2017 *)

concat(0, Vec(-2*x*(x^5-4*x^4-3*x^3+7*x^2-7*x+3)/((x-1)^2*(x^6-7*x^5+x^4+6*x^3-11*x^2+7*x-1)) + O(x^100))) \\ Colin Barker, Nov 06 2014

a(n) = 9a(n-1) - 26a(n-2) + 35a(n-3) - 22a(n-4) - 3a(n-5) + 16a(n-6) - 9a(n-7) + a(n-8). - David Radcliffe, Jan 19 2001

G.f.: -2*x*(x^5-4*x^4-3*x^3+7*x^2-7*x+3) / ((x-1)^2*(x^6-7*x^5+x^4+6*x^3-11*x^2+7*x-1)). - Colin Barker, Nov 06 2014

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

A339136 Number of (undirected) cycles in the graph C_3 X P_n.

Original entry on oeis.org

1, 14, 63, 220, 701, 2154, 6523, 19640, 59001, 177094, 531383, 1594260, 4782901, 14348834, 43046643, 129140080, 387420401, 1162261374, 3486784303, 10460353100, 31381059501, 94143178714, 282429536363, 847288609320, 2541865828201, 7625597484854, 22876792454823, 68630377364740

Offset: 1

Seiichi Manyama, Nov 25 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A059020, A339074, A339137, A339140, A339142, A339143.

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339136(n):
    universe = make_CnXPk(3, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339136(n) for n in range(1, 20)])

Empirical g.f.: -x*(9*x+1) / ((x-1)^2 * (3*x-1)). - Vaclav Kotesovec, Dec 09 2020

A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

Original entry on oeis.org

1, 6, 37, 750, 459829, 210067308558, 44127887746326310604917, 1947270476915296449559791701269341583074001038

Offset: 0

Giovanni Resta, May 05 2017

A perfect (sometimes called complete) binary tree of height k has 2^(k+1)-1 nodes.

a(8) has 91 digits and thus it is not reported.

Alois P. Heinz, Table of n, a(n) for n = 0..11
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Types of binary trees

Cf. A003095, 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[1]=b[1]=1; b[n_] := b[n] = 1 + b[n - 1]^2; a[n_] := a[n] = b[n]^2 + 2 a[n - 1]; Array[a, 8]

Let b(0)=1 and b(n) = 1+b(n-1)^2. Then, a(0)=1 and a(n) = b(n)^2 + 2*a(n-1). Note that b(n) = A003095(n+1).

A286191 a(n) = (2^n-1)^2 + 2*n.

Original entry on oeis.org

3, 13, 55, 233, 971, 3981, 16143, 65041, 261139, 1046549, 4190231, 16769049, 67092507, 268402717, 1073676319, 4294836257, 17179607075, 68718952485, 274876858407, 1099509530665, 4398042316843, 17592177655853, 70368727400495, 281474943156273, 1125899839733811

Offset: 1

Giovanni Resta, May 05 2017

Number of connected induced (non-null) subgraphs of the complete bipartite graph K(n,n).

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

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_] := (2^n-1)^2 + 2*n; Array[a, 30]
Table[(2^n - 1)^2 + 2 n, {n, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
LinearRecurrence[{8, -21, 22, -8}, {3, 13, 55, 233}, 20] (* Eric W. Weisstein, Aug 09 2017 *)
CoefficientList[Series[(3 - 11 x + 14 x^2)/((-1 + x)^2 (1 - 6 x + 8 x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 09 2017 *)

Vec(x*(3 - 11*x + 14*x^2) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 30 2017

a(n) = (2^n-1)^2 + 2*n.
From Colin Barker, May 30 2017: (Start)
G.f.: x*(3 - 11*x + 14*x^2) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)).
a(n) = 8*a(n-1) - 21*a(n-2) + 22*a(n-3) - 8*a(n-4) for n>4.
(End)

Name changed to the formula by Eric W. Weisstein, Aug 09 2017

A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with n nodes.

Original entry on oeis.org

1, 3, 6, 10, 17, 24, 37, 51, 78, 110, 173, 229, 340, 477, 750, 1024, 1571, 2253, 3616, 5024, 7839, 11356, 18389, 25173, 38740, 55697, 89610, 124870, 195389, 283536, 459829, 636123, 988710, 1429442, 2310905, 3227617, 5061040, 7352817, 11936370, 16526444

Offset: 1

Giovanni Resta, May 05 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..5651 (first 255 terms from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Types of binary trees

Cf. A285934, 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).

Join[{1}, Table[g=KaryTree[n]; -1 + ParallelSum[Boole@ConnectedGraphQ@Subgraph[g, s], {s, Subsets@Range[n]}], {n, 2, 16}]]
(* Second program: *)
l[n_] := With[{h = 2^Floor[Log[2, n]]}, Min[h - 1, n - h/2]];
b[n_] := b[n] = 1 + If[n <= 1, n, b[l[n]]*b[n - 1 - l[n]]];
a[n_] := a[n] = If[n <= 1, n, b[n] - 1 + a[l[n]] + a[n - 1 - l[n]]];
Array[a, 40] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

l(n)={my(h=2^floor(log(n)/log(2))); min(h-1,n-h/2)}
b(n)=1+if(n<=1,n,b(l(n))*b(n-1-l(n)));
a(n)=if(n<=1,n,b(n)-1 + a(l(n)) + a(n-1-l(n))); \\ Andrew Howroyd, May 22 2017

a(2^k-1) = A285934(k-1).

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

A356828 Number of vertex cuts in the n-ladder graph P_2 x P_n.

Original entry on oeis.org

0, 2, 23, 147, 748, 3414, 14719, 61495, 252364, 1024938, 4137207, 16639339, 66775964, 267631726, 1071801407, 4290282671, 17168559452, 68692172578, 274811988823, 1099352487299, 4397662311948, 17591258505542, 70366504900671, 281469570617703, 1125886855379628

Offset: 1

Eric W. Weisstein, Aug 30 2022

Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Vertex Cut
Index entries for linear recurrences with constant coefficients, signature (8,-20,16,1,-4).

Cf. A059020.

Table[4^n + 2 n + (10 - LucasL[n + 3, 2])/4, {n, 20}]
LinearRecurrence[{8, -20, 16, 1, -4}, {0, 2, 23, 147, 748}, 20]
CoefficientList[Series[x (2 + x) (1 + 3 x)/((-1 + x)^2 (-1 + 4 x) (-1 + 2 x + x^2)), {x, 0, 20}], x]

a(n) = 4^n + 2*n + (10 - LucasL(n + 3, 2))/4.
a(n) = 8*a(n-1) - 20*a(n-2) + 16*a(n-3) + a(n-4) - 4*a(n-5).
G.f.: x^2*(2+x)*(1+3*x)/((-1+x)^2*(-1+4*x)*(-1+2*x + x^2)).
a(n) = 2^(2*n) - A059020(n) - 1. - Pontus von Brömssen, Aug 30 2022

cp's OEIS Frontend

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

A285765 Number of connected induced (non-null) subgraphs of the n X n queen graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A059021 Number of 3 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

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A339136 Number of (undirected) cycles in the graph C_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A286191 a(n) = (2^n-1)^2 + 2*n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A286304 Number of connected induced (non-null) subgraphs of the complete binary tree with n nodes.