A163695 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.

2, 5, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803

Offset: 1

Author

R. H. Hardin, Aug 03 2009

Keywords

• nonn
• easy

Examples

			All solutions for n=4:
...0.1...0.1...1.1...1.1...1.0...1.1...1.0...1.1...1.0...1.0...0.1
...0.1...0.1...0.1...0.1...1.0...1.0...1.0...1.0...1.1...1.1...1.1
...0.1...0.1...0.1...0.1...1.1...1.1...1.0...1.0...0.1...0.1...1.0
...0.1...1.1...0.1...1.1...0.1...0.1...1.1...1.1...0.1...1.1...1.1
		

Links

• R. H. Hardin, Table of n, a(n) for n=1..100
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Crossrefs

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

Cf. A288219.

Programs

PARI

Vec(x*(2 - x)*(1 + x)^2 / (1 - x - x^2) + O(x^60)) \\ Colin Barker, Feb 20 2018

Formula

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

[The Transfer Matrix Method provides this recurrence. - R. J. Mathar, Aug 02 2017]

From Colin Barker, Feb 20 2018: (Start)

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

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

(End)