A163029 Number of n X 3 binary arrays with all 1's connected and a path of 1's from top row to bottom row.

6, 28, 144, 730, 3692, 18666, 94384, 477264, 2413346, 12203374, 61707810, 312032874, 1577831334, 7978491800, 40344192708, 204005208738, 1031576601204, 5216289773894, 26376789637884, 133377373911160, 674438554337506

Offset: 1

Author

R. H. Hardin, Jul 20 2009

Keywords

• nonn

Links

• R. H. Hardin, Table of n, a(n) for n = 1..100
• Chaim Goodman-Strauss, Notes on the number of m × n binary arrays with all 1’s connected and a path of 1’s from top row to bottom row (May 21 2020)
• Chaim Goodman-Strauss, Mma notebook to accompany the above document

Crossrefs

Cf. A001333 ((n-1) X 2 arrays), A059021 (no path required).

Cf. also A163030, A163031, A163032, A163033, A163034, A163035, A163036.

Formula

a(n) = 7*a(n-1) - 11*a(n-2) + 6*a(n-3) + a(n-4) - 7*a(n-5) + a(n-6). [Conjectured by R. J. Mathar, Aug 11 2009]

Proof from Peter Kagey, May 08 2019: Scanning from top to bottom, there are 6 possible intermediate states that the bottom row can be in. The transitions between these states define a 6 X 6 transition matrix whose characteristic polynomial agrees with the characteristic polynomial of the above recurrence. QED

For an alternative proof see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020