A287151 -id:A287151 - cp's OEIS frontend

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

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

A359993 Array read by antidiagonals: T(m,n) is the number of connected spanning subgraphs in the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 23, 23, 1, 1, 105, 431, 105, 1, 1, 479, 7857, 7857, 479, 1, 1, 2185, 142625, 555195, 142625, 2185, 1, 1, 9967, 2587279, 38757695, 38757695, 2587279, 9967, 1, 1, 45465, 46929343, 2698167665, 10286937043, 2698167665, 46929343, 45465, 1

Offset: 1

Andrew Howroyd, Jan 28 2023

Also T(m,n) except when m = n = 0 is the number of connected edge covers in the m X n grid graph.

			Table starts:
=================================================================
m\n| 1    2       3          4             5                6
---+-------------------------------------------------------------
1  | 1    1       1          1             1                1 ...
2  | 1    5      23        105           479             2185 ...
3  | 1   23     431       7857        142625          2587279 ...
4  | 1  105    7857     555195      38757695       2698167665 ...
5  | 1  479  142625   38757695   10286937043    2711895924889 ...
6  | 1 2185 2587279 2698167665 2711895924889 2692324030864335 ...
   ...

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

Rows 1..4 are A000012, A107839(n-1), A158453, A359991.
Main diagonal is A359992.
Cf. A116469 (spanning trees), A287151 (connected induced subgraphs), A286912 (edge covers), A359990 (edge cuts), A360194 (spanning forests).

T(m,n) = T(n,m).

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

A378941 Number of Motzkin paths of length n up to reversal.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset: 0

Andrew Howroyd, Dec 17 2024

nonn

A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

			The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ Thomas Scheuerle, Dec 18 2024

a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

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

Original entry on oeis.org

0, 15, 275, 5726, 116166, 2301877, 45280509, 889477656, 17470103108, 343131620201, 6739543393711, 132373673619692, 2599998546891870, 51067506790572861, 1003035296281103375, 19700977608538546036, 386953998564799463776, 7600302885548184827385, 149280286962228069289683

Offset: 0

Andrew Howroyd, Dec 18 2024

nonn

Equivalently, the number of connected (non-null) induced subgraphs in the grid graph P_5 X P_n.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, order 33.

Row 5 of A287151.

cp's OEIS Frontend

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

A359993 Array read by antidiagonals: T(m,n) is the number of connected spanning subgraphs in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

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

A378941 Number of Motzkin paths of length n up to reversal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs