A163696 Number of n X 3 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.

3, 11, 28, 63, 138, 298, 642, 1371, 2908, 6146, 12970, 27351, 57654, 121502, 256026, 539459, 1136632, 2394830, 5045754, 10631039, 22398786, 47192482, 99430802, 209492731, 441384340, 929961258, 1959353418, 4128199671, 8697783790, 18325528950, 38610411434, 81349022659

Offset

1,1

Comments

Same recurrence for A163715 and A163734.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000 (terms 1..57 from R. H. Hardin)

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

Formula

Empirical: a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3) + a(n-4) - 2*a(n-5) + a(n-6) for n>=10.

Empirical g.f.: x*(3 - x - x^2 + x^4 + 5*x^6 - x^7 - 2*x^8) / ((1 - x)^2*(1 - 2*x - x^4)). - Colin Barker, Feb 22 2018

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

Example

All solutions for n=2:
...0.0.1...0.1.1...0.0.1...0.1.1...1.1.1...0.0.1...1.1.1...0.1.0...1.1.0
...0.0.1...0.0.1...0.1.1...0.1.1...0.0.1...1.1.1...1.0.1...0.1.1...0.1.1
------
...1.0.0...1.0.1
...1.1.1...1.1.1

Crossrefs

Column 3 of A391823.

Cf. A163715, A163734.

Sequence in context: A119074 A211810 A182260 * A092781 A332669 A391645

Adjacent sequences: A163693 A163694 A163695 * A163697 A163698 A163699

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved