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

Comments

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

Links

Table of n, a(n) for n=1..45.

Eric Weisstein's World of Mathematics, Edge Cut

Eric Weisstein's World of Mathematics, Grid Graph

Formula

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

Example

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

Crossrefs

Rows 1..3 are A000225(n-1), A359987, A359988.

Main diagonal is A359989.

Cf. A141387, A359993 (connected spanning subgraphs).

Sequence in context: A244237 A238683 A303114 * A170856 A176781 A349407

Adjacent sequences: A359987 A359988 A359989 * A359991 A359992 A359993

Keyword

nonn,tabl

Author

Andrew Howroyd, Jan 28 2023

Status

approved