login
A369892
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.
1
1, 3, 1, 7, 7, 1, 15, 37, 17, 1, 31, 175, 197, 41, 1, 63, 781, 1985, 1041, 99, 1, 127, 3367, 18621, 22193, 5503, 239, 1, 255, 14197, 167337, 433801, 247759, 29089, 577, 1, 511, 58975, 1461797, 8057625, 10056087, 2764991, 153769, 1393, 1, 1023, 242461, 12519345, 144762849, 384409519, 232777209, 30856705, 812849, 3363, 1
OFFSET
1,2
COMMENTS
Similar to A359576 but disallowing Up steps.
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)
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.
EXAMPLE
For the 37 2 X 3 grids, see A359576.
The following 4 X 5 grid is a counterexample that is counted by A359576 but not by the present sequence:
10000
10111
11101
00001
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.
Table starts:
1 3 7 15 31 63 127 ...
1 7 37 175 781 3367 14197 ...
1 17 197 1985 18621 167337 1461797 ...
1 41 1041 22193 433801 8057625 144762849 ...
1 99 5503 247759 10056087 384409519 ...
1 239 29089 2764991 232777209 ...
1 577 153769 30856705 ...
1 1393 812849 ...
1 3363 ...
1 ...
...
CROSSREFS
First 3 rows are A000225, A005061, A069361.
First 4 columns are A000012, A001333, A069378, A069379.
Cf. A359576 (up steps allowed).
Sequence in context: A372968 A188463 A374839 * A359576 A319298 A101748
KEYWORD
nonn,tabl
AUTHOR
Caleb Stanford, Feb 05 2024
STATUS
approved