A369892 - OEIS

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, 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

(list; table; graph; refs; listen; history; text; internal format)

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

Table of n, a(n) for n=1..55.

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 ...

...