login
Half the number of (n+1) X 2 binary arrays with no 2X2 subblock having exactly 2 ones.
2

%I #29 Jan 09 2025 08:02:30

%S 2,5,13,33,85,217,557,1425,3653,9353,23965,61377,157237,402745,

%T 1031693,2642673,6769445,17340137,44417917,113778465,291450133,

%U 746563993,1912364525,4898620497,12548078597,32142560585,82334874973,210905117313,540244617205,1383865086457,3544843555277

%N Half the number of (n+1) X 2 binary arrays with no 2X2 subblock having exactly 2 ones.

%C a(n) appears to be sum of the elements of the n-th power of the matrix {{1, 2}, {2, 0}}. - _Griffin N. Macris_, Mar 25 2016

%C Let b(n) and c(n) be the number of such arrays where the two values in the bottom row are equal and not equal respectively so that a(n) = (1/2)*(b(n) + c(n)). Then b(n) and c(n) satisfy the recursive equations b(n+1) = b(n) + 2*c(n) and c(n+1) = 2*b(n). These equations correspond to the observation above and lead to an order 2 linear recurrence for a(n). - _Andrew Howroyd_, Jan 09 2025

%H R. H. Hardin, <a href="/A183774/b183774.txt">Table of n, a(n) for n = 0..200</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,4).

%F a(n) = a(n-1) + 4*a(n-2).

%F a(n) = (sqrt(17)/34)*((21 + 5*sqrt(17))*(1/2 + sqrt(17)/2)^(n-1) - (21 - 5*sqrt(17))*(1/2 - sqrt(17)/2)^(n-1)). - _Taras Goy_, Jan 04 2025

%F G.f.: (2 + 3*x)*(1 - x - 4*x^2). - _Andrew Howroyd_, Jan 09 2025

%e Some solutions with a(1,1)=0 for 3 X 2:

%e ..0..1....0..0....0..1....0..1....0..1....0..0....0..0....0..1....0..0....0..0

%e ..1..1....0..1....1..1....0..0....0..0....0..1....1..0....1..1....0..0....1..0

%e ..1..1....0..0....1..0....1..0....0..0....1..1....1..1....0..1....0..0....0..0

%o (PARI) a(n)=vecsum([1,1]*[1,2;2,0]^n) \\ _Andrew Howroyd_, Jan 09 2025

%Y Column 1 of A183782.

%K nonn

%O 0,1

%A _R. H. Hardin_, Jan 07 2011

%E a(0) = 2 prepended by _Andrew Howroyd_, Jan 09 2025