login
Number of n X 2 binary arrays with all 1s connected, a path of 1s from top row to lower right corner, and no 1 having more than two 1s adjacent.
4

%I #16 Feb 20 2018 04:27:32

%S 2,5,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,

%T 15127,24476,39603,64079,103682,167761,271443,439204,710647,1149851,

%U 1860498,3010349,4870847,7881196,12752043,20633239,33385282,54018521,87403803

%N Number of n X 2 binary arrays with all 1s connected, a path of 1s from top row to lower right corner, and no 1 having more than two 1s adjacent.

%H R. H. Hardin, <a href="/A163695/b163695.txt">Table of n, a(n) for n=1..100</a>

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

%F a(n) = a(n-1) + a(n-2) for n>=5.

%F [The Transfer Matrix Method provides this recurrence. - _R. J. Mathar_, Aug 02 2017]

%F From _Colin Barker_, Feb 20 2018: (Start)

%F G.f.: x*(2 - x)*(1 + x)^2 / (1 - x - x^2).

%F a(n) = (2^(-1-n)*((1-sqrt(5))^n*(-5+sqrt(5)) + (1+sqrt(5))^n*(5+sqrt(5)))) / sqrt(5) for n>2.

%F (End)

%e All solutions for n=4:

%e ...0.1...0.1...1.1...1.1...1.0...1.1...1.0...1.1...1.0...1.0...0.1

%e ...0.1...0.1...0.1...0.1...1.0...1.0...1.0...1.0...1.1...1.1...1.1

%e ...0.1...0.1...0.1...0.1...1.1...1.1...1.0...1.0...0.1...0.1...1.0

%e ...0.1...1.1...0.1...1.1...0.1...0.1...1.1...1.1...0.1...1.1...1.1

%o (PARI) Vec(x*(2 - x)*(1 + x)^2 / (1 - x - x^2) + O(x^60)) \\ _Colin Barker_, Feb 20 2018

%Y It appears that A163714 and A163733 have the same recurrence as this sequence.

%Y Cf. A288219.

%K nonn,easy

%O 1,1

%A _R. H. Hardin_, Aug 03 2009