A369892 - OEIS

%I #31 Feb 09 2024 04:40:59

%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,433801,247759,29089,577,

%U 1,511,58975,1461797,8057625,10056087,2764991,153769,1393,1,1023,242461,12519345,144762849,384409519,232777209,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 using only left, right, and downward steps.

%C Similar to A359576 but disallowing Up steps.

%C The sequences are initially similar but differ for 4 X 5 grids (433801 instead of 433809), 4 X 6 grids (8057625 instead of 8057905), and 5 X 5 grids (10056087 instead of 10056959)

%C Can be calculated by dynamic programming from 1 X n grids to m X n grids by keeping track of the number of grids with each of the 2^n patterns of reachable squares in the last row.

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

%e For the 37 2 X 3 grids, see A359576.

%e The following 4 X 5 grid is a counterexample that is counted by A359576 but not by the present sequence:

%e     10000

%e     10111

%e     11101

%e     00001

%e Notice that there is a path of 1s from the top to the bottom, but only via the upward step detour in the third column. There are 8 such 4 X 5 grids, formed from the above by reflection and by toggling the first row, second column and last row, second to last column.

%e Table starts:

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

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

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

%e     1     41     1041      22193      433801     8057625   144762849 ...

%e     1     99     5503     247759    10056087   384409519   ...

%e     1    239    29089    2764991   232777209   ...

%e     1    577   153769   30856705   ...

%e     1   1393   812849   ...

%e     1   3363   ...

%e     1   ...

%e     ...

%Y First 3 rows are A000225, A005061, A069361.

%Y First 4 columns are A000012, A001333, A069378, A069379.

%Y Cf. A359576 (up steps allowed).

%K nonn,tabl

%O 1,2

%A _Caleb Stanford_, Feb 05 2024