|
%I #7 Jan 28 2023 18:25:01
%S 0,1,1,3,11,3,7,105,105,7,15,919,3665,919,15,31,7713,123215,123215,
%T 7713,31,63,63351,4051679,16222021,4051679,63351,63,127,514321,
%U 131630449,2108725953,2108725953,131630449,514321,127,255,4148839,4248037953,272179739279,1089224690733,272179739279,4248037953,4148839,255
%N Array read by antidiagonals: T(m,n) is the number of edge cuts in the grid graph P_m X P_n.
%C 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).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCut.html">Edge Cut</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%F 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.
%F T(m,n) = T(n,m).
%e Table starts:
%e ========================================================
%e m\n| 1 2 3 4 5
%e ---+----------------------------------------------------
%e 1 | 0 1 3 7 15 ...
%e 2 | 1 11 105 919 7713 ...
%e 3 | 3 105 3665 123215 4051679 ...
%e 4 | 7 919 123215 16222021 2108725953 ...
%e 5 | 15 7713 4051679 2108725953 1089224690733 ...
%e 6 | 31 63351 131630449 272179739279 560238057496423 ...
%e ...
%Y Rows 1..3 are A000225(n-1), A359987, A359988.
%Y Main diagonal is A359989.
%Y Cf. A141387, A359993 (connected spanning subgraphs).
%K nonn,tabl
%O 1,4
%A _Andrew Howroyd_, Jan 28 2023
|
