A167071 Number of spanning trees in G X P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 5}}.

4, 1376, 361860, 92544256, 23575404820, 6002044445280, 1527898117755412, 388939442019315712, 99007542753465378420, 25203122804459545322080, 6415645979596681028789108, 1633151297922105531036929280, 415731036835959295502046104100, 105827485262836457484100780941664

Offset

1,1

References

F. Faase, On the number of specific spanning subgraphs of the graphs A X P_n, Ars Combin. 49 (1998), 129-154.

Links

P. Raff, Table of n, a(n) for n = 1..200

P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.

P. Raff, Analysis of the Number of Spanning Trees of G x P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 5}}. Contains sequence, recurrence, generating function, and more.

P. Raff, Analysis of the Number of Spanning Trees of Grid Graphs.

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

Index entries for sequences related to trees

Formula

a(n) = 344 a(n-1)

- 25540 a(n-2)

+ 745448 a(n-3)

- 10445708 a(n-4)

+ 76194968 a(n-5)

- 303860988 a(n-6)

+ 687124520 a(n-7)

- 899525622 a(n-8)

+ 687124520 a(n-9)

- 303860988 a(n-10)

+ 76194968 a(n-11)

- 10445708 a(n-12)

+ 745448 a(n-13)

- 25540 a(n-14)

+ 344 a(n-15)

- a(n-16)

G.f.: -4x (x^14 -2331x^12 +56416x^11 -467115x^10 +1546624x^9 -1949983x^8 +1949983x^6 -1546624x^5 +467115x^4 -56416x^3 +2331x^2 -1)/ (x^16 -344x^15 +25540x^14 -745448x^13 +10445708x^12 -76194968x^11 +303860988x^10 -687124520x^9 +899525622x^8 -687124520x^7 +303860988x^6 -76194968x^5 +10445708x^4 -745448x^3 +25540x^2 -344x+1).

Crossrefs

Sequence in context: A283260 A217601 A172925 * A274296 A283103 A278844

Adjacent sequences: A167068 A167069 A167070 * A167072 A167073 A167074

Keyword

nonn

Author

Paul Raff

Status

approved