login
Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with a path of adjacent 1's from top row to bottom row.
14

%I #28 Feb 09 2024 04:03:16

%S 1,3,1,7,7,1,15,37,17,1,31,175,197,41,1,63,781,1985,1041,99,1,127,

%T 3367,18621,22193,5503,239,1,255,14197,167337,433809,247759,29089,577,

%U 1,511,58975,1461797,8057905,10056959,2764991,153769,1393,1,1023,242461,12519345,144769425,384479935,232824241,30856705,812849,3363,1

%N Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with a path of adjacent 1's from top row to bottom row.

%C The grid has m rows and n columns.

%C "Path" refers to a sequence of L(eft), R(ight), U(p), D(own) steps (edge connectivity like in fixed polyominoes), self-avoiding, starting anywhere in the first row and ending anywhere in the last row. The path does not need to step on all 1's of the array. The path has obviously at least m-1 steps. - _R. J. Mathar_, Jun 21 2023

%C Note that the total would be smaller if Up steps were disallowed (as in the original comment above); the smallest grid size for which this phenomenon occurs is 4 X 5. The total number of 4 X 5 and 5 X 5 grids would be 433801 instead of 433809 and 10056087 instead of 10056959, respectively, without Up steps. - _Caleb Stanford_, Feb 01 2024

%H Caleb Stanford, <a href="https://github.com/cdstanford/curiosities/tree/master/fish-friendly">Rust program to compute the sequence</a>

%H Utah Math Olympiad 2022, <a href="https://utahmath.org/doc/2022UtahMathOlympiad.pdf">Problem 6</a>

%e Array begins:

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

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

%e ---+----------------------------------------------------------------

%e 1 | 1 3 7 15 31 63 127 ...

%e 2 | 1 7 37 175 781 3367 14197 ...

%e 3 | 1 17 197 1985 18621 167337 1461797 ...

%e 4 | 1 41 1041 22193 433809 8057905 144769425 ...

%e 5 | 1 99 5503 247759 10056959 384479935 14142942975 ...

%e 6 | 1 239 29089 2764991 232824241 18287614751 1374273318721 ...

%e 7 | 1 577 153769 30856705 5388274121 868972410929 ...

%e ...

%e All the 37 2 X 3 binary arrays:

%e 001 001 001 001

%e 001 011 101 111 plus 4 copies left-right flipped

%e .

%e 010 010 010 010

%e 010 011 110 111

%e .

%e 011 011 011 011 011 011

%e 001 010 011 101 110 111 plus 6 copies left-right flipped

%e .

%e 101 101 101 101 101 101

%e 001 011 100 101 110 111

%e .

%e 111 111 111 111 111 111 111

%e 001 010 011 100 101 110 111 - _R. J. Mathar_, Jun 21 2023

%Y Main diagonal is A365988.

%Y Rows 1..19 are A000225, A005061, A069361, A069362, A069363-A069377.

%Y Columns 1..20 are A000012, A001333(n+1), A069378, A069379, A069380-A069395.

%Y Cf. A359574, A359575.

%K nonn,tabl

%O 1,2

%A _Andrew Howroyd_, Jan 06 2023

%E One additional diagonal of terms added by _Caleb Stanford_, Feb 05 2024