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, 126491972, 204668310

Offset

1,1

Comments

Same recurrence for A163695 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

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)

From Andrew Howroyd, Dec 24 2025: (Start)

The above empirical formulas confirmed using the transfer matrix method.

a(n) = 2*Fibonacci(n + 2) for n >= 3. (End)

Example

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

Crossrefs

Essentially the same as A090991, A078642, A047992. - R. J. Mathar, Aug 06 2009

Column 2 of A391822.

Sequence in context: A114113 A100056 A359147 * A333910 A307191 A234638

Adjacent sequences: A163711 A163712 A163713 * A163715 A163716 A163717

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved