A359993 -id:A359993 - cp's OEIS frontend

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

0, 1, 1, 3, 11, 3, 7, 105, 105, 7, 15, 919, 3665, 919, 15, 31, 7713, 123215, 123215, 7713, 31, 63, 63351, 4051679, 16222021, 4051679, 63351, 63, 127, 514321, 131630449, 2108725953, 2108725953, 131630449, 514321, 127, 255, 4148839, 4248037953, 272179739279, 1089224690733, 272179739279, 4248037953, 4148839, 255

Offset: 1

Andrew Howroyd, Jan 28 2023

The complement of an edge cut is a disconnected spanning subgraph (spanning meaning that the graph has the same vertex set although some vertices may be of degree zero).

			Table starts:
========================================================
m\n|  1     2         3            4               5
---+----------------------------------------------------
1  |  0     1         3            7              15 ...
2  |  1    11       105          919            7713 ...
3  |  3   105      3665       123215         4051679 ...
4  |  7   919    123215     16222021      2108725953 ...
5  | 15  7713   4051679   2108725953   1089224690733 ...
6  | 31 63351 131630449 272179739279 560238057496423 ...
   ...

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

Rows 1..3 are A000225(n-1), A359987, A359988.
Main diagonal is A359989.
Cf. A141387, A359993 (connected spanning subgraphs).

T(m,n) = 2^B(m,n) - A359993(m,n) where B(m,n) = 2*m*n - m - n = A141387(n+m-2, n-1) is the number of edges in the graph.

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

A360194 Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 4, 15, 4, 8, 112, 112, 8, 16, 836, 3102, 836, 16, 32, 6240, 85818, 85818, 6240, 32, 64, 46576, 2373870, 8790016, 2373870, 46576, 64, 128, 347648, 65664106, 900013270, 900013270, 65664106, 347648, 128, 256, 2594880, 1816344222, 92146956300, 341008617408, 92146956300, 1816344222, 2594880, 256

Offset: 1

Andrew Howroyd, Jan 29 2023

Acyclic spanning subgraphs are also called spanning forests.

			Table starts:
========================================================
m\n|  1     2        3           4               5
---+----------------------------------------------------
1  |  1     2        4           8              16 ...
2  |  2    15      112         836            6240 ...
3  |  4   112     3102       85818         2373870 ...
4  |  8   836    85818     8790016       900013270 ...
5  | 16  6240  2373870   900013270    341008617408 ...
6  | 32 46576 65664106 92146956300 129187804977182 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Acyclic Graph
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1..4 are A000079(n-1), A022026(n-1), A158450, A360195.
Main diagonal is A080691.
Cf. A116469 (spanning trees), A359993 (connected spanning subgraphs), A360202.

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Original entry on oeis.org

1, 5, 431, 555195, 10286937043, 2692324030864335, 9852929684161379901975, 501079193080617800221189943995, 352690403996687922642590703716802346343, 3426297680513758764075706102615040790667832304415, 458508006189588425325361635000918336126387961057365005349963

Offset: 1

Andrew Howroyd, Jan 28 2023

nonn

For n > 1, a(n) is the number of connected edge covers in the n X n grid graph.

			The a(2) = 5 connected spanning subgraphs are the following subgraphs and their rotations and reflections.
   o---o   o---o
   |       |   |
   o---o   o---o

Andrew Howroyd, Table of n, a(n) for n = 1..15
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A359993.

Cf. A007341, A053765, A080691, A286913, A359989.

a(n) = A053765(n) - A359989(n).

A158453 Number of connected spanning subgraphs in 3 X n grid.

Original entry on oeis.org

1, 23, 431, 7857, 142625, 2587279, 46929343, 851213073, 15439417633, 280042119887, 5079439221503, 92131506968913, 1671092849279201, 30310492056413839, 549775513106272063, 9971897330025100689, 180871526632046468257, 3280670474584477332047, 59505213248435614382975

Offset: 1

Alois P. Heinz, Mar 19 2009

Alois P. Heinz, Table of n, a(n) for n = 1..250
Index entries for linear recurrences with constant coefficients, signature (22,-73,54,-8).

Column k=3 of A359993.

a:= n-> (Matrix([[23, 1, 0, 1/4]]). Matrix(4, (i, j)-> `if`(i=j-1, 1,
           `if`(j=1, [22, -73, 54, -8][i], 0)))^n)[1, 3]:
seq(a(n), n=1..20);

G.f.: (2*x^3-x^2-x) / (54*x^3-73*x^2-1+22*x-8*x^4).

A359991 Number of connected spanning subgraphs in the 4 X n grid graph.

Original entry on oeis.org

1, 105, 7857, 555195, 38757695, 2698167665, 187715481077, 13057666054455, 908271228919067, 63177423571626685, 4394479113198329137, 305669914361091938915, 21261697652022553831895, 1478914849135091196256585, 102869919107895518546358701

Offset: 1

Andrew Howroyd, Jan 28 2023

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (105,-2907,33255,-183316,519800,-778624,610800,-237312,39680,-2048).

Row 4 of A359993.

G.f.: x*(1 - 261*x^2 + 2190*x^3 - 5940*x^4 + 5400*x^5 - 672*x^6 - 960*x^7 + 256*x^8)/(1 - 105*x + 2907*x^2 - 33255*x^3 + 183316*x^4 - 519800*x^5 + 778624*x^6 - 610800*x^7 + 237312*x^8 - 39680*x^9 + 2048*x^10).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A360194 Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A158453 Number of connected spanning subgraphs in 3 X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A359991 Number of connected spanning subgraphs in the 4 X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Formula