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,1

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

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

Crossrefs

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

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

Sequence in context: A216383 A283094 A110047 * A309490 A344755 A045722

Adjacent sequences: A163026 A163027 A163028 * A163030 A163031 A163032

Keyword

nonn

Author

R. H. Hardin, Jul 20 2009

Status

approved