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

%I #25 Feb 16 2025 08:32:43

%S 0,6,40,218,1126,5726,28992,146642,741556,3749816,18961450,95880894,

%T 484833212,2451616864,12396892316,62686360476,316981037374,

%U 1602852315476,8105013367472,40983964057352,207240288658392

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

%C 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

%H Colin Barker, <a href="/A059021/b059021.txt">Table of n, a(n) for n = 0..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (9,-26,35,-22,-3,16,-9,1).

%F 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

%F 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

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

%t LinearRecurrence[{9, -26, 35, -22, -3, 16, -9, 1}, {6, 40, 218, 1126, 5726, 28992, 146642, 741556}, 20] (* _Eric W. Weisstein_, Aug 09 2017 *)

%o (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

%Y Row 3 of A287151.

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

%K nonn,easy,changed

%O 0,2

%A _John W. Layman_, Dec 14 2000