A163714 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, 7, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

Author

R. H. Hardin, Aug 03 2009

Keywords

• nonn

Comments

Same recurrence for A163695.

Same recurrence for A163733.

Examples

			All solutions for n=4:
...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
...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
...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
...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
------
...1.1...0.1...0.1
...0.1...1.1...1.1
...1.1...1.0...1.0
...1.0...1.0...1.1
		

Links

• R. H. Hardin, Table of n, a(n) for n=1..100

Crossrefs

Cf. A090991, A078642, A047992. - R. J. Mathar, Aug 06 2009

Formula

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

Conjectures from Colin Barker, Feb 22 2018: (Start)

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

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

(End)