

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.


8



6, 28, 144, 730, 3692, 18666, 94384, 477264, 2413346, 12203374, 61707810, 312032874, 1577831334, 7978491800, 40344192708, 204005208738, 1031576601204, 5216289773894, 26376789637884, 133377373911160, 674438554337506
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


LINKS

R. H. Hardin, Table of n, a(n) for n = 1..100
Chaim GoodmanStrauss, 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 GoodmanStrauss, Mma notebook to accompany the above document


FORMULA

a(n) = 7*a(n1)  11*a(n2) + 6*a(n3) + a(n4)  7*a(n5) + a(n6). [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 GoodmanStrauss links.  N. J. A. Sloane, May 22 2020


CROSSREFS

Cf. A001333 ((n1) X 2 arrays).
Cf. also A163030, A163031, A163032, A163033, A163034, A163035, A163036.
Sequence in context: A216383 A283094 A110047 * A309490 A045722 A047129
Adjacent sequences: A163026 A163027 A163028 * A163030 A163031 A163032


KEYWORD

nonn


AUTHOR

R. H. Hardin, Jul 20 2009


STATUS

approved



