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

%I #9 Feb 22 2018 06:17:07

%S 3,7,10,16,26,42,68,110,178,288,466,754,1220,1974,3194,5168,8362,

%T 13530,21892,35422,57314,92736,150050,242786,392836,635622,1028458,

%U 1664080,2692538,4356618,7049156,11405774,18454930,29860704,48315634,78176338

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

%C Same recurrence for A163695.

%C Same recurrence for A163733.

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

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

%F Conjectures from _Colin Barker_, Feb 22 2018: (Start)

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

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

%F (End)

%e All solutions for n=4:

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

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

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

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

%e ------

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

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

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

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

%Y Cf. A090991, A078642, A047992. - _R. J. Mathar_, Aug 06 2009

%K nonn

%O 1,1

%A _R. H. Hardin_, Aug 03 2009