A368809 -id:A368809 - cp's OEIS frontend

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

Offset: 1

Caleb Stanford, Feb 05 2024

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.
Each row and each column satisfies a linear recurrence with constant coefficients. - Pontus von Brömssen, Feb 05 2025

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

Caleb Stanford, Rust program to compute the sequence.

First 4 rows are A000225, A005061, A069361, A368809.
First 4 columns are A000012, A001333, A069378, A069379.
Cf. A359576 (up steps allowed).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs