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

8, 4128, 1688680, 674251008, 268240730440, 106651712835360, 42400091291143144, 16856142798678061056, 6701134268084528945960, 2664024512087857705508640, 1059078313836124682324459656, 421034736344698799106102063360, 167381624605785919658488535740200

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

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

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, 3}, {2, 4}, {3, 5}}. Contains sequence, recurrence, generating function, and more.

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

Index entries for sequences related to trees

Formula

a(n) = 516 a(n-1)

- 51460 a(n-2)

+ 1809612 a(n-3)

- 29405308 a(n-4)

+ 244066452 a(n-5)

- 1071197628 a(n-6)

+ 2573753820 a(n-7)

- 3447217942 a(n-8)

+ 2573753820 a(n-9)

- 1071197628 a(n-10)

+ 244066452 a(n-11)

- 29405308 a(n-12)

+ 1809612 a(n-13)

- 51460 a(n-14)

+ 516 a(n-15)

- a(n-16)

G.f.: -8x(x^14 -3711x^12 +105264x^11 -1019095x^10 +3723456x^9 -4971063x^8 +4971063x^6 -3723456x^5 +1019095x^4 -105264x^3 +3711x^2 -1) / (x^16 -516x^15 +51460x^14 -1809612x^13 +29405308x^12 -244066452x^11 +1071197628x^10 -2573753820x^9 +3447217942x^8 -2573753820x^7 +1071197628x^6 -244066452x^5 +29405308x^4 -1809612x^3 +51460x^2 -516x +1).

Crossrefs

Sequence in context: A060760 A203436 A159368 * A303895 A305287 A304900

Adjacent sequences: A167062 A167063 A167064 * A167066 A167067 A167068

Keyword

nonn

Author

Paul Raff

Status

approved