A163685 Number of n X 2 binary arrays with all 1s connected, a path of 1s from upper left corner to lower right corner, and no 1 having more than two 1s adjacent.

1, 3, 5, 8, 13, 20, 32, 52, 85, 138, 223, 360, 582, 942, 1525, 2468, 3993, 6460, 10452, 16912, 27365, 44278, 71643, 115920, 187562, 303482, 491045, 794528, 1285573, 2080100, 3365672, 5445772, 8811445, 14257218, 23068663, 37325880, 60394542, 97720422, 158114965

Offset

1,2

Links

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

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

Formula

Empirical: a(n) = 2*a(n-1) - a(n-2) + a(n-4) for n >= 7.

From R. J. Mathar, Aug 11 2009: (Start)

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

Empirical: a(n) = (5*A000045(n) - A010892(n+1))/2, n>2. (End)

Formulas confirmed using the transfer matrix method. - Andrew Howroyd, Dec 24 2025

Example

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

Crossrefs

Row 2 of A391818.

Sequence in context: A265067 A265068 A227547 * A080614 A079122 A265069

Adjacent sequences: A163682 A163683 A163684 * A163686 A163687 A163688

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved