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, 141422324, 228826127

Offset

1,1

Comments

Same recurrence as A163714 and A163733.

Links

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

Index entries for linear recurrences with constant coefficients, signature (1,1).

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)

Example

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

Prog

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

Crossrefs

Essentially the same as A288219.

Column 2 of A391823.

Cf. A163714, A163733.

Sequence in context: A247052 A386096 A364649 * A134641 A162491 A152216

Adjacent sequences: A163692 A163693 A163694 * A163696 A163697 A163698

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved