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.
LINKS
Caleb Stanford, Rust program to compute the sequence.
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
KEYWORD
nonn,tabl
AUTHOR
Caleb Stanford, Feb 05 2024
STATUS
approved