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, 3410378763941290, 17244985831165254, 87201321877047490

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.

Index entries for linear recurrences with constant coefficients, signature (7,-11,6,1,-7,1).

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

G.f.: 2*x*(3 - 7*x + 7*x^2 - 3*x^3 - 4*x^4 + x^5)/(1 - 7*x + 11*x^2 - 6*x^3 - x^4 + 7*x^5 - x^6). - Andrew Howroyd, Dec 24 2025

Crossrefs

Column 3 of A359574.

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

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

Sequence in context: A283094 A380551 A110047 * A309490 A344755 A045722

Adjacent sequences: A163026 A163027 A163028 * A163030 A163031 A163032

Keyword

nonn,easy

Author

R. H. Hardin, Jul 20 2009

Status

approved