A378934 -id:A378934 - cp's OEIS frontend

A378932 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the grid graph P_m X P_n.

0, 1, 1, 2, 6, 2, 3, 15, 15, 3, 4, 28, 53, 28, 4, 5, 45, 146, 146, 45, 5, 6, 66, 356, 627, 356, 66, 6, 7, 91, 809, 2471, 2471, 809, 91, 7, 8, 120, 1759, 9292, 16213, 9292, 1759, 120, 8, 9, 153, 3716, 33878, 103196, 103196, 33878, 3716, 153, 9, 10, 190, 7702, 120771, 642364, 1123743, 642364, 120771, 7702, 190, 10

Offset: 1

Andrew Howroyd, Dec 11 2024

T(m,n) is the number of partitionings of an m X n checkerboard into two edgewise-connected sets.

			Table starts:
===================================================
m\n | 1  2    3     4      5        6         7 ...
----+----------------------------------------------
  1 | 0  1    2     3      4        5         6 ...
  2 | 1  6   15    28     45       66        91 ...
  3 | 2 15   53   146    356      809      1759 ...
  4 | 3 28  146   627   2471     9292     33878 ...
  5 | 4 45  356  2471  16213   103196    642364 ...
  6 | 5 66  809  9292 103196  1123743  12028981 ...
  7 | 6 91 1759 33878 642364 12028981 221984391 ...
  ...

Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimal Edge Cut.

Main diagonal is A068416.
Rows 1..4 are A001477(n-1), A000384, A378933, A378934.
Rows 3..8 multiplied by 2 are A166761, A166766, A166769, A166771, A166773, A166774.
Cf. A287151, A359990.

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

A378933 Number of minimal edge cuts in the 3 X n grid graph.

Original entry on oeis.org

2, 15, 53, 146, 356, 809, 1759, 3716, 7702, 15763, 31993, 64582, 129912, 260749, 522627, 1046616, 2094858, 4191639, 8385533, 16773690, 33550412, 67104305, 134212583, 268429676, 536864446, 1073734619, 2147475649, 4294958446, 8589924832, 17179858453

Offset: 1

Andrew Howroyd, Dec 11 2024

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Row 3 of A378932.

Cf. A166761, A359988, A378934.

LinearRecurrence[{6, -14, 16, -9, 2}, {2, 15, 53, 146, 356}, 30] (* Paolo Xausa, Mar 02 2025 *)

a(n) = {16*2^n - (2*n^3 + 9*n^2 + 73*n + 96)/6}

a(n) = 16*2^n - (2*n^3 + 9*n^2 + 73*n + 96)/6.
G.f.: x*(2 + 3*x - 9*x^2 + 6*x^3)/((1 - 2*x)*(1 - x)^4).
a(n) = A166761(n)/2.

A166766 Number of n X 4 1..2 arrays containing at least one of each value, and all equal values connected.

Original entry on oeis.org

6, 56, 292, 1254, 4942, 18584, 67756, 241542, 846502, 2927816, 10023380, 34042358, 114900334, 385933816, 1291392908, 4308452150, 14341213590, 47651315192, 158111069492, 524063522870, 1735584459598, 5744207323976, 19002070568572, 62835884445574, 207725012781046, 686552300486040

Offset: 1

R. H. Hardin, Oct 21 2009

nonn

			Some solutions for n=4
...1.1.1.1...2.2.1.1...2.2.2.2...1.1.2.2...2.2.2.2...2.1.1.1...2.2.2.2
...1.2.1.1...2.1.1.1...1.2.1.2...2.1.1.2...1.1.2.1...2.2.1.1...2.2.2.2
...1.2.1.2...2.1.1.1...1.2.1.1...2.1.2.2...1.1.1.1...2.2.1.1...1.2.2.1
...2.2.2.2...1.1.1.1...1.1.1.1...2.2.2.2...1.1.1.1...2.1.1.1...1.1.1.1
------
...2.2.2.2...2.2.2.2...2.2.1.1...1.1.2.1...2.1.1.1...1.1.1.1...1.1.2.2
...2.1.1.1...1.1.1.2...1.2.2.1...1.1.2.1...2.1.2.2...1.2.1.2...1.1.1.1
...1.1.1.1...1.1.2.2...1.2.1.1...1.1.1.1...2.1.2.2...1.2.2.2...1.1.1.1
...1.1.1.1...2.2.2.2...1.1.1.1...1.1.1.1...2.2.2.2...1.1.2.2...1.1.1.1

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (10,-37,59,-27,-25,21,5,-4,-1).

Twice row 4 of A378932.

Cf. A378934.

a(n) = 2*A378934(n). - Andrew Howroyd, Dec 12 2024

a(16) onwards from Andrew Howroyd, Dec 12 2024

cp's OEIS Frontend

A378932 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A378933 Number of minimal edge cuts in the 3 X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A166766 Number of n X 4 1..2 arrays containing at least one of each value, and all equal values connected.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions