A069361 -id:A069361 - cp's OEIS frontend

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

3, 16, 84, 440, 2304, 12064, 63168, 330752, 1731840, 9068032, 47480832, 248612864, 1301753856, 6816071680, 35689414656, 186872201216, 978475548672, 5123364487168, 26826284728320, 140464250421248, 735480363614208, 3851025180000256, 20164229625544704, 105581277033267200

Offset: 1

R. H. Hardin, Mar 22 2002

			From _Andrew Howroyd_, Oct 27 2020: (Start)
Some of the 2*a(2) = 32 arrays are:
  0 0   0 0   0 0   0 1   0 1   0 0   0 1
  0 0   0 1   1 1   1 0   1 0   1 1   1 0
  1 1   1 1   1 1   1 1   0 1   0 0   1 1
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-4).

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.

Cf. A084326.

LinearRecurrence[{6, -4}, {3, 16}, 100] (* Jean-François Alcover, Nov 01 2020 *)

Vec((3 - 2*x)/(1 - 6*x + 4*x^2) + O(x^30)) \\ Andrew Howroyd, Oct 27 2020

a(n) = 2^(n-1)*fibonacci(2*n+2) \\ Andrew Howroyd, Oct 27 2020

Empirical G.f.: x*(3-2*x)/(1-6*x+4*x^2).  - Colin Barker, Feb 22 2012
Empirical: a(n) = 3*A084326(n) - 2*A084326(n-1). - R. J. Mathar, Nov 09 2018
From Andrew Howroyd, Oct 27 2020: (Start)
The above conjectures are true and follow from formulas given in A069361 and A069396.
a(n) = (8^n)/2 - A069361(n) + A069396(n).
a(n) = 2^(n-1)*Fibonacci(2*n+2) = A084326(n+1)/2. (End)

Terms a(21) and beyond from Andrew Howroyd, Oct 27 2020

A069395 Number of n X 20 binary arrays with a path of adjacent 1's from top row to bottom row.

Original entry on oeis.org

1048575, 1096024843375, 1117982939085627425, 1092719640470296684383473

Offset: 1

R. H. Hardin, Mar 22 2002

nonn

Cf. 1 X n A000225, 2 X n A005061, n X 2 A001333, 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.

A069452 Half the number of 7 X n binary arrays with no path of adjacent 1's or adjacent 0's from top to bottom or side to side.

Original entry on oeis.org

63, 56757, 18772467, 3912171001

Offset: 2

R. H. Hardin, Mar 22 2002

nonn

Cf. 2 X n 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.

A069396 Half the number of 3 X n binary arrays with a path of adjacent 1's and a path of adjacent 0's from top row to bottom row.

Original entry on oeis.org

1, 25, 377, 4541, 48329, 476389, 4461489, 40306317, 354713977, 3060942133, 26020259201, 218626028573, 1820140085705, 15043088032837, 123602247055953, 1010793162739629, 8234370308667673, 66870924588036181

Offset: 2

R. H. Hardin, Mar 22 2002

nonn

G. C. Greubel, Table of n, a(n) for n = 2..1000

Cf. 1 X n A000225, 2 X n A016269, 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.

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

Drop[CoefficientList[Series[x^2*(2*x+1)^2/(1-8*x)/(2*x^2-7*x + 1)/(4*x^2 - 6*x + 1), {x, 0, 50}], x], 2] (* G. C. Greubel, Apr 22 2018 *)

x='x+O('x^30); Vec(x^2*(2*x+1)^2/(1-8*x)/(2*x^2-7*x+1)/(4*x^2 -6*x+1)) \\ G. C. Greubel, Apr 22 2018

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

2*a(n) = 8^n+A084326(n+1) -2*A186446(n). - R. J. Mathar, May 09 2023

A069416 Half the number of n X 16 binary arrays with a path of adjacent 1's and a path of adjacent 0's from top row to bottom row.

Original entry on oeis.org

32767, 2104469695, 123602247055953, 6475978445076745163

Offset: 1

R. H. Hardin, Mar 22 2002

nonn

Cf. 1 X n A000225, 2 X n A016269, 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.

A069417 Number of 3 X n 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, 15, 147, 1231, 9539, 70679, 509019, 3596367, 25070707, 173088903, 1186544331, 8090866303, 54950124515, 372067098167, 2513408596923, 16948369098159, 114128268554323, 767705581586151, 5159843165163435, 34657637020377055, 232672006452068291, 1561421588852637335

Offset: 1

R. H. Hardin, Mar 22 2002

			From _Andrew Howroyd_, Oct 27 2020: (Start)
Some of the a(2) = 15 arrays are:
  1 0   1 0   1 0   1 1   1 0
  1 1   1 0   1 1   1 1   1 1
  1 0   1 1   1 1   1 1   0 1
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (13,-48,40,-8).

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.

LinearRecurrence[{13, -48, 40, -8}, {1, 15, 147, 1231}, 25] (* Paolo Xausa, Feb 08 2024 *)

Vec((1 + 2*x)/((1 - 7*x + 2*x^2)*(1 - 6*x + 4*x^2)) + O(x^25)) \\ Andrew Howroyd, Oct 27 2020

From Andrew Howroyd, Oct 27 2020: (Start)
a(n) = A069361(n) - 2*A069396(n).
a(n) = 13*a(n-1) - 48*a(n-2) + 40*a(n-3) - 8*a(n-4) for n > 4.
G.f.: x*(1 + 2*x)/((1 - 7*x + 2*x^2)*(1 - 6*x + 4*x^2)).
(End)

Terms a(12) and beyond from Andrew Howroyd, Oct 27 2020

A069428 Number of n X 8 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, 6305, 3596367, 1201461339

Offset: 1

R. H. Hardin, Mar 22 2002

nonn

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.

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

Original entry on oeis.org

256, 1731840, 3334295986, 3616567402784

Offset: 2

R. H. Hardin, Mar 22 2002

nonn

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.

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

Original entry on oeis.org

3, 35, 269, 1723, 10123, 56757, 309755, 1663515, 8846821, 46767491, 246319875, 1294402053, 6792548971, 35614277883, 186632524741, 977711862035, 5120933346419

Offset: 2

R. H. Hardin, Mar 22 2002

nonn

Cf. 2 X n 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.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A069395 Number of n X 20 binary arrays with a path of adjacent 1's from top row to bottom row.

Views

Author

Keywords

Crossrefs

A069452 Half the number of 7 X n binary arrays with no path of adjacent 1's or adjacent 0's from top to bottom or side to side.

Views

Author

Keywords

Crossrefs

A069396 Half the number of 3 X n binary arrays with a path of adjacent 1's and a path of adjacent 0's from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A069416 Half the number of n X 16 binary arrays with a path of adjacent 1's and a path of adjacent 0's from top row to bottom row.

Views

Author

Keywords

Crossrefs

A069417 Number of 3 X n 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

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A069428 Number of n X 8 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

Crossrefs

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

Views

Author

Keywords

Crossrefs

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

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