A287151 - OEIS

%I #14 Feb 16 2025 08:33:46

%S 1,3,3,6,13,6,10,40,40,10,15,108,218,108,15,21,275,1126,1126,275,21,

%T 28,681,5726,11506,5726,681,28,36,1664,28992,116166,116166,28992,1664,

%U 36,45,4040,146642,1168586,2301877,1168586,146642,4040,45,55,9779,741556,11749134,45280509,45280509,11749134,741556,9779,55

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

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

%C 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

%H Andrew Howroyd, <a href="/A287151/b287151.txt">Table of n, a(n) for n = 1..435</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/InducedSubgraph.html">Induced Subgraph</a>

%e Table starts:

%e ====================================================================

%e m\n|  1    2      3        4         5           6             7

%e ---|----------------------------------------------------------------

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

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

%e 3  |  6   40    218     1126      5726       28992        146642 ...

%e 4  | 10  108   1126    11506    116166     1168586      11749134 ...

%e 5  | 15  275   5726   116166   2301877    45280509     889477656 ...

%e 6  | 21  681  28992  1168586  45280509  1732082741   66037462454 ...

%e 7  | 28 1664 146642 11749134 889477656 66037462454 4872949974666 ...

%e ...

%Y Rows 2..5 are A059020, A059021, A059524, A378940.

%Y Main diagonal is A059525.

%Y Cf. A116469, A140662, A286139, A286189, A292357, A378941.

%K nonn,tabl,changed

%O 1,2

%A _Andrew Howroyd_, May 20 2017