A287151 - OEIS

A287151

Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 218, 108, 15, 21, 275, 1126, 1126, 275, 21, 28, 681, 5726, 11506, 5726, 681, 28, 36, 1664, 28992, 116166, 116166, 28992, 1664, 36, 45, 4040, 146642, 1168586, 2301877, 1168586, 146642, 4040, 45, 55, 9779, 741556, 11749134, 45280509, 45280509, 11749134, 741556, 9779, 55

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also the number of connected induced (non-null) subgraphs of the grid graph P_m X P_n.

All rows (or columns) are linear recurrences with constant coefficients and the order of the recurrence of row m is at most 1 + A378941(m+1). At least for columns up to 7, this bound gives the actual order of the recurrence. The second differences of any column give those arrays that touch the top and bottom boundaries and have a recurrence order of 2 less since a finite state machine to enumerate these does not require states for empty rows. The number of states required is also considered in A140662 but does not take symmetry into account. - Andrew Howroyd, Dec 18 2024

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..435

Eric Weisstein's World of Mathematics, Connected Graph

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Induced Subgraph

EXAMPLE

Table starts:

====================================================================

m\n| 1 2 3 4 5 6 7

---|----------------------------------------------------------------

1 | 1 3 6 10 15 21 28 ...

2 | 3 13 40 108 275 681 1664 ...