OFFSET
1,1
COMMENTS
Column 2 of A295051.
From - Mikhail Lavrov, Oct 31 2022: (Start)
If the first row is 0 0, the array can continue with anything; there are a(n-1) such arrays for n > 1.
If the first row is 1 1, then the second row must be 1 1, and the third row must be 0 0; there are a(n-3) such arrays for n > 3.
If the first row is 1 0 or 0 1, then the rows after that can alternate between 0 1 and 1 0 for any number of steps before going to 0 0 (or reaching the end); there are 2(a(n-2) + a(n-3) + ...) such arrays for n > 2. This gives a(n) = a(n-1) + a(n-3) + 2(a(n-2) + a(n-3) + ...); to simplify the recurrence, apply it to a(n) - a(n-1), getting a(n) - a(n-1) = a(n-1) - a(n-2) + a(n-3) - a(n-4) + 2a(n-2). This proves Colin Barker's recurrence relation below for n > 4. (End)
LINKS
R. H. Hardin, Table of n, a(n) for n = 1..210
Index entries for linear recurrences with constant coefficients, signature (2, 1, 1, -1).
FORMULA
Empirical: a(n) = 2*a(n-1) + a(n-2) + a(n-3) - a(n-4).
Empirical g.f.: x*(3 + 2*x - x^3) / (1 - 2*x - x^2 - x^3 + x^4). - Colin Barker, Feb 21 2018
EXAMPLE
Some solutions for n=7:
0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0
1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1
1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 0
0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0
0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0
MATHEMATICA
LinearRecurrence[{2, 1, 1, -1}, {3, 8, 19, 48}, 30] (* Mikhail Lavrov, Nov 01 2022 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
R. H. Hardin, Nov 13 2017
STATUS
approved