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,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).

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

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

Cf. A288219.

Sequence in context: A224320 A247052 A364649 * A134641 A162491 A152216

Adjacent sequences: A163692 A163693 A163694 * A163696 A163697 A163698

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved