A163686 Number of n X 3 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, 5, 17, 39, 83, 175, 375, 807, 1732, 3690, 7805, 16441, 34605, 72893, 153653, 323917, 682654, 1438292, 3030059, 6383675, 13449863, 28338555, 59708355, 125801331, 265051912, 558439806, 1176585241, 2478972461, 5223002977, 11004454185, 23185495457, 48849950873, 102922882178

Offset

1,2

Links

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

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

Formula

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

Empirical g.f.: x*(1 + 2*x^2 - 6*x^3 + 10*x^4 - 4*x^5 - 2*x^6 + 4*x^7 + 6*x^8 + 2*x^9 - 3*x^10 - 2*x^11) / ((1 - x)^2*(1 - x + x^2 + x^3)*(1 - 2*x - x^4)). - Colin Barker, Mar 25 2018

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

Example

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

Crossrefs

Row 3 of A391818.

Sequence in context: A127744 A122734 A250413 * A147165 A147257 A146645

Adjacent sequences: A163683 A163684 A163685 * A163687 A163688 A163689

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved