A359987 -id:A359987 - 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).

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

Original entry on oeis.org

3, 105, 3665, 123215, 4051679, 131630449, 4248037953, 136587740399, 4382607093471, 140457446235441, 4498520188148993, 144023056568886959, 4610014925578108703, 147543642097619999089, 4721816707356538941633, 151105755554498621737583, 4835522406931884652356447

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 (54,-777,2390,-1736,256).

Row 3 of A359990.

Cf. A013823, A158453, A359987.

Vec((3 - 57*x + 326*x^2 - 280*x^3 + 32*x^4)/((1 - 32*x)*(1 - 22*x + 73*x^2 - 54*x^3 + 8*x^4)) + O(x^20))

a(n) = 54*a(n-1) - 777*a(n-2) + 2390*a(n-3) - 1736*a(n-4) + 256*a(n-5) for n > 5.
G.f.: x*(3 - 57*x + 326*x^2 - 280*x^3 + 32*x^4)/((1 - 32*x)*(1 - 22*x + 73*x^2 - 54*x^3 + 8*x^4)).
a(n) = A013823(n-1) - A158453(n).

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