A359575 -id:A359575 - cp's OEIS frontend

A069325 Number of 3 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

1, 8, 51, 295, 1632, 8830, 47239, 251261, 1332456, 7055228, 37327007, 197404203, 1043751584, 5518106750, 29171471659, 154210451661, 815197197636, 4309313949364, 22779900825195, 120418887728947

Offset: 1

R. H. Hardin, Mar 16 2002

Charles R Greathouse IV, Table of n, a(n) for n = 1..1383
Index entries for linear recurrences with constant coefficients, signature (9,-21,3,24,-8,-4,4).

Row 3 of A359575.

Cf. 2 X n A048739, 4 X n A069326, 5 X n A069327, 6 X n A069328, 7 X n A069329, 8 X n A069330, 9 X n A069331, 10 X n A069332, 11 X n A069333, 12 X n A069334, 13 X n A069335, 14 X n A069336, 15 X n A069337, 16 X n A069338, 17 X n A069339, 18 X n A069340, 19 X n A069341, 20 X n A069342, n X n A069343, n X n symmetric A069344.

m:=25; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(x*(1-x+x^3)/((1-2*x-2*x^2)*(2*x^5-4*x^4+x^3+9*x^2-7*x+1)))); // G. C. Greubel, Apr 22 2018

CoefficientList[Series[x*(1-x+x^3)/((1-2*x-2*x^2)*(2*x^5-4*x^4+x^3+9*x^2 -7*x+1)), {x, 0, 50}], x] (* G. C. Greubel, Apr 22 2018 *)
LinearRecurrence[{9,-21,3,24,-8,-4,4},{1,8,51,295,1632,8830,47239},20] (* Harvey P. Dale, May 21 2023 *)

Vec(-x*(1-x+x^3)/(2*x^2+2*x-1)/(2*x^5-4*x^4+x^3+9*x^2-7*x+1) + O(x^99)) \\ Charles R Greathouse IV, Jun 12 2015

G.f.: x*(1-x+x^3)/((1-2*x-2*x^2)*(2*x^5-4*x^4+x^3+9*x^2-7*x+1)). - Vladeta Jovovic, Jul 02 2003

A069343 Number of n X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Original entry on oeis.org

1, 3, 51, 3828, 1225194, 1636193228, 9009490924794, 203037531986079710, 18633578769242938930634, 6939491897974410047045467672, 10460300685270373054347943215411456, 63693144523237155451684426136374621458792, 1564268765712262926681452283892583850491065259004

Offset: 1

R. H. Hardin, Mar 16 2002

nonn

Cf. m X n A069325-A069342, n X n symmetric A069344.

Main diagonal of A359575.

a(8)-a(13) from Sean A. Irvine, Apr 29 2024

A069326 Number of 4 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Original entry on oeis.org

1, 20, 295, 3828, 46557, 546286, 6279393, 71316632, 804230945, 9031118936, 101161197895, 1131456031256, 12643706576681, 141214773950750, 1576695869980497, 17600838146781308, 196457931325141165

Offset: 1

R. H. Hardin, Mar 16 2002

nonn

Row 4 of A359575.

Cf. 2 X n A048739, 3 X n A069325, 5 X n A069327, 6 X n A069328, 7 X n A069329, 8 X n A069330, 9 X n A069331, 10 X n A069332, 11 X n A069333, 12 X n A069334, 13 X n A069335, 14 X n A069336, 15 X n A069337, 16 X n A069338, 17 X n A069339, 18 X n A069340, 19 X n A069341, 20 X n A069342, n X n A069343, n X n symmetric A069344.

A069327 Number of 5 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Original entry on oeis.org

1, 49, 1632, 46557, 1225194, 30754544, 749866185, 17950397258, 424660442975, 9969967594443, 232909647253690, 5423397612311731, 126017939209370356, 2924071505958808678, 67786971099219351975, 1570519781573431498844

Offset: 1

R. H. Hardin, Mar 16 2002

nonn

Row 5 of A359575.

Cf. 2 X n A048739, 3 X n A069325, 4 X n A069326, 6 X n A069328, 7 X n A069329, 8 X n A069330, 9 X n A069331, 10 X n A069332, 11 X n A069333, 12 X n A069334, 13 X n A069335, 14 X n A069336, 15 X n A069337, 16 X n A069338, 17 X n A069339, 18 X n A069340, 19 X n A069341, 20 X n A069342, n X n A069343, n X n symmetric A069344.

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.

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

A359573 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from upper left corner to lower right corner.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 8, 1, 1, 20, 45, 20, 1, 1, 49, 234, 234, 49, 1, 1, 119, 1193, 2423, 1193, 119, 1, 1, 288, 6049, 24455, 24455, 6049, 288, 1, 1, 696, 30616, 245972, 482443, 245972, 30616, 696, 1, 1, 1681, 154861, 2473317, 9469361, 9469361, 2473317, 154861, 1681, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

			Array begins:
================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   1     1       1         1           1             1 ...
2  | 1   3     8      20        49         119           288 ...
3  | 1   8    45     234      1193        6049         30616 ...
4  | 1  20   234    2423     24455      245972       2473317 ...
5  | 1  49  1193   24455    482443     9469361     185899132 ...
6  | 1 119  6049  245972   9469361   360923899   13742823032 ...
7  | 1 288 30616 2473317 185899132 13742823032 1012326365581 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435

Main diagonal is A163002.
Rows 1..10 are A000012, A048739(n-1), A163003, A163004, A163005, A163006, A163007, A163008, A163009, A163010.
Cf. A287151, A359574, A359575, A359576.

T(m,n) = T(n,m).

cp's OEIS Frontend

A069325 Number of 3 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A069343 Number of n X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Views

Author

Keywords

Crossrefs

Extensions

A069326 Number of 4 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Views

Author

Keywords

Crossrefs

A069327 Number of 5 X n binary arrays with path of adjacent 1's from upper right corner to lower left corner.

Views

Author

Keywords

Crossrefs

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

A359573 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from upper left corner to lower right corner.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula