A069378 -id:A069378 - cp's OEIS frontend

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

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, 433809, 247759, 29089, 577, 1, 511, 58975, 1461797, 8057905, 10056959, 2764991, 153769, 1393, 1, 1023, 242461, 12519345, 144769425, 384479935, 232824241, 30856705, 812849, 3363, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

The grid has m rows and n columns.
"Path" refers to a sequence of L(eft), R(ight), U(p), D(own) steps (edge connectivity like in fixed polyominoes), self-avoiding, starting anywhere in the first row and ending anywhere in the last row. The path does not need to step on all 1's of the array. The path has obviously at least m-1 steps. - R. J. Mathar, Jun 21 2023
Note that the total would be smaller if Up steps were disallowed (as in the original comment above); the smallest grid size for which this phenomenon occurs is 4 X 5. The total number of 4 X 5 and 5 X 5 grids would be 433801 instead of 433809 and 10056087 instead of 10056959, respectively, without Up steps. - Caleb Stanford, Feb 01 2024
Each row and each column satisfies a linear recurrence with constant coefficients. - Pontus von Brömssen, Feb 05 2025

			Array begins:
====================================================================
m\n| 1   2      3        4          5            6             7
---+----------------------------------------------------------------
1  | 1   3      7       15         31           63           127 ...
2  | 1   7     37      175        781         3367         14197 ...
3  | 1  17    197     1985      18621       167337       1461797 ...
4  | 1  41   1041    22193     433809      8057905     144769425 ...
5  | 1  99   5503   247759   10056959    384479935   14142942975 ...
6  | 1 239  29089  2764991  232824241  18287614751 1374273318721 ...
7  | 1 577 153769 30856705 5388274121 868972410929 ...
  ...
All the 37 2 X 3 binary arrays:
001 001 001 001
001 011 101 111 plus 4 copies left-right flipped
.
010 010 010 010
010 011 110 111
.
011 011 011 011 011 011
001 010 011 101 110 111 plus 6 copies left-right flipped
.
101 101 101 101 101 101
001 011 100 101 110 111
.
111 111 111 111 111 111 111
001 010 011 100 101 110 111 - _R. J. Mathar_, Jun 21 2023

Samuel Dittmer, Hiram Golze, Grant Molnar, and Caleb Stanford, Puzzle and Proof: A Decade of Problems from the Utah Math Olympiad, CRC Press, 2025, p. 51.

Caleb Stanford, Rust program to compute the sequence.
Utah Math Olympiad 2022, Problem 6.

Main diagonal is A365988.
Rows 1..19 are A000225, A005061, A069361, A069362, A069363-A069377.
Columns 1..20 are A000012, A001333(n+1), A069378, A069379, A069380-A069395.
Cf. A359574, A359575.

One additional diagonal of terms added by Caleb Stanford, Feb 05 2024

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.

Original entry on oeis.org

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

A069423 Number of n X 3 binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row.

Original entry on oeis.org

1, 19, 147, 907, 5149, 28159, 151331, 806463, 4280141, 22670199, 119955523, 634412111, 3354416225, 17734138519, 93751306327, 495600489243, 2619870168133, 13849199313235, 73209594712831, 386999645945759, 2045750897807901, 10814208630415211, 57165847109895879

Offset: 1

R. H. Hardin, Mar 22 2002

Index entries for linear recurrences with constant coefficients, signature (11,-41,64,-35,-13,25,-12,2).

Cf. 2 X n A001047, n X 2 A034182, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

a(n) = A069378(n) - 2 * A069403(n). - Sean A. Irvine, Aug 23 2024

G.f.: x*(2*x^7-10*x^6+23*x^5-18*x^4-5*x^3+21*x^2-8*x-1) / ((x-1)*(x^2-3*x+1)*(2*x^5-4*x^4+x^3+9*x^2-7*x+1)). - Alois P. Heinz, Aug 23 2024

More terms from Sean A. Irvine, Aug 23 2024

A069441 Half the number of n X 3 binary arrays with no path of adjacent 1's or adjacent 0's from top row to bottom row.

Original entry on oeis.org

0, 4, 84, 1074, 11058, 102448, 896026, 7578952, 62820362, 514178822, 4174954460, 33725176208, 271523097884, 2181288088576, 17498432045552, 140241880816930, 1123280018219562, 8993350007112124, 71984384316723134, 576073752326317448, 4609640266662591130

Offset: 1

R. H. Hardin, Mar 22 2002

Cf. 2 X n A000079, n X 1 A000225, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

a(n) = 2^(3*n-1) - A069378(n) + A069403(n). - Sean A. Irvine, Aug 23 2024

More terms from Sean A. Irvine, Aug 23 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

A069423 Number of n X 3 binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A069441 Half the number of n X 3 binary arrays with no path of adjacent 1's or adjacent 0's from top row to bottom row.

Views

Author

Keywords

Crossrefs

Formula

Extensions