A360194 -id:A360194 - cp's OEIS frontend

A080691 Number of spanning forests of the n X n grid graph.

1, 15, 3102, 8790016, 341008617408, 181075508242067552, 1315927389374152034113856, 130877523274817580209987036404864, 178135975585132088643635627145305047963624, 3318089946193080260596185780557019330240985991363200, 845810281460839114896541390288164525407725177643901666416522016

Offset: 1

Andre Poenitz [André Pönitz], Peter Tittmann, Mar 03 2003

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..15
N. Calkin, C. Merino, S. Noble and M. Noy, Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice, The Electronic Journal of Combinatorics, Volume 10(1), 2003, #R4.
A. Pönitz, Über eine Methode zur Konstruktion von Algorithmen für die Berechnung von Invarianten in endlichen ungerichteten Hypergraphen, PhD Thesis (2004) C.3.
Peter Tittmann, More Results [Gives a(1)-a(14)]
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360194.

Cf. A007341, A080690.

Terms a(10) and beyond from Andrew Howroyd, Feb 22 2023

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

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 23, 23, 1, 1, 105, 431, 105, 1, 1, 479, 7857, 7857, 479, 1, 1, 2185, 142625, 555195, 142625, 2185, 1, 1, 9967, 2587279, 38757695, 38757695, 2587279, 9967, 1, 1, 45465, 46929343, 2698167665, 10286937043, 2698167665, 46929343, 45465, 1

Offset: 1

Andrew Howroyd, Jan 28 2023

Also T(m,n) except when m = n = 0 is the number of connected edge covers in the m X n grid graph.

			Table starts:
=================================================================
m\n| 1    2       3          4             5                6
---+-------------------------------------------------------------
1  | 1    1       1          1             1                1 ...
2  | 1    5      23        105           479             2185 ...
3  | 1   23     431       7857        142625          2587279 ...
4  | 1  105    7857     555195      38757695       2698167665 ...
5  | 1  479  142625   38757695   10286937043    2711895924889 ...
6  | 1 2185 2587279 2698167665 2711895924889 2692324030864335 ...
   ...

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

Rows 1..4 are A000012, A107839(n-1), A158453, A359991.
Main diagonal is A359992.
Cf. A116469 (spanning trees), A287151 (connected induced subgraphs), A286912 (edge covers), A359990 (edge cuts), A360194 (spanning forests).

T(m,n) = T(n,m).

A158450 Number of spanning forests in 3 X n grid.

Original entry on oeis.org

1, 4, 112, 3102, 85818, 2373870, 65664106, 1816344222, 50242141946, 1389754592846, 38442187035914, 1063354458854270, 29413589398458778, 813613216256931886, 22505463603889302698, 622526628016224886878, 17219792020736937982522, 476318961941184616298510

Offset: 0

Alois P. Heinz, Mar 19 2009

			For n = 1 the a(1) = 4 forests are 1.2.3, 1-2.3, 1.2-3, 1-2-3.

Alois P. Heinz, Table of n, a(n) for n = 0..250
Index entries for linear recurrences with constant coefficients, signature (33,-154,176,-32).

Row 3 of A360194.

a:= n-> ceil((Matrix([[112, 4, 1/8, 0]]). Matrix(4, (i, j)-> if i=j-1 then 1 elif j=1 then [33, -154, 176, -32][i] else 0 fi)^n)[1, 3]):
seq(a(n), n=0..20);

G.f.: (28*x^4-154*x^3+134*x^2-29*x+1)/(32*x^4-176*x^3+154*x^2-33*x+1).

a(0) inserted by Alois P. Heinz, Jan 23 2013

A360195 Number of acyclic spanning subgraphs in the 4 X n grid graph.

Original entry on oeis.org

8, 836, 85818, 8790016, 900013270, 92146956300, 9434262852690, 965904015750408, 98891686243392270, 10124779093041746052, 1036600283636692454794, 106129737227642833341248, 10865828704552798371380934, 1112470797598979236296844092, 113897550673086022197853291458

Offset: 1

Andrew Howroyd, Jan 29 2023

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (146,-5145,74504,-525120,1885344,-3430128,3147392,-1418496,278528,-16384).

Row 4 of A360194.

Cf. A003696, A359991.

G.f.: x*(8 - 332*x + 4922*x^2 - 34224*x^3 + 120160*x^4 - 215504*x^5 + 196576*x^6 - 88512*x^7 + 17408*x^8 - 1024*x^9)/(1 - 146*x + 5145*x^2 - 74504*x^3 + 525120*x^4 - 1885344*x^5 + 3430128*x^6 - 3147392*x^7 + 1418496*x^8 - 278528*x^9 + 16384*x^10).

cp's OEIS Frontend

A080691 Number of spanning forests of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A158450 Number of spanning forests in 3 X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A360195 Number of acyclic spanning subgraphs in the 4 X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Formula