A360194 Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.

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

Author

Andrew Howroyd, Jan 29 2023

Keywords

• nonn
• tabl

Comments

Acyclic spanning subgraphs are also called spanning forests.

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..435
• Eric Weisstein's World of Mathematics, Acyclic Graph
• Eric Weisstein's World of Mathematics, Grid Graph

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.