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

Author

John W. Layman, Dec 14 2000

Keywords

• nonn
• easy

Comments

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

Links

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

Crossrefs

Row 3 of A287151.

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

Programs

Mathematica

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

PARI

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

Formula

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