login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295045 Number of n X 2 0..1 arrays with each 1 horizontally or vertically adjacent to 0 or 2 1s. 4

%I #20 Mar 04 2024 00:17:54

%S 3,8,19,48,120,299,747,1865,4656,11625,29024,72464,180921,451705,

%T 1127771,2815704,7029963,17551696,43821288,109408531,273160083,

%U 681998289,1702743904,4251237649,10614057408,26500098080,66162747313,165188412465

%N Number of n X 2 0..1 arrays with each 1 horizontally or vertically adjacent to 0 or 2 1s.

%C Column 2 of A295051.

%C From - _Mikhail Lavrov_, Oct 31 2022: (Start)

%C If the first row is 0 0, the array can continue with anything; there are a(n-1) such arrays for n > 1.

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

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

%H R. H. Hardin, <a href="/A295045/b295045.txt">Table of n, a(n) for n = 1..210</a>

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

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

%F Empirical g.f.: x*(3 + 2*x - x^3) / (1 - 2*x - x^2 - x^3 + x^4). - _Colin Barker_, Feb 21 2018

%e Some solutions for n=7:

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

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

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

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

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

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

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

%t LinearRecurrence[{2, 1, 1, -1}, {3, 8, 19, 48}, 30] (* _Mikhail Lavrov_, Nov 01 2022 *)

%Y Cf. A295051.

%K nonn

%O 1,1

%A _R. H. Hardin_, Nov 13 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)