login
A359990
Array read by antidiagonals: T(m,n) is the number of edge cuts in the grid graph P_m X P_n.
4
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
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
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Jan 28 2023
STATUS
approved