login
A360194
Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.
5
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,2
COMMENTS
Acyclic spanning subgraphs are also called spanning forests.
LINKS
Eric Weisstein's World of Mathematics, Acyclic Graph
Eric Weisstein's World of Mathematics, Grid Graph
EXAMPLE
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 ...
...
CROSSREFS
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.
Sequence in context: A153959 A308847 A006205 * A268073 A204685 A205161
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Jan 29 2023
STATUS
approved