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

3, 1005, 250848, 60075885, 14263332015, 3379514561280, 800337094071879, 189513130911442365, 44873808170614072416, 10625354802279238810125, 2515898969449422698378427, 595720806457312484163072000, 141056237447350542048435569739

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, 3}, {4, 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) = 335 a(n-1)

- 26224 a(n-2)

+ 744035 a(n-3)

- 10084457 a(n-4)

+ 72968360 a(n-5)

- 295849710 a(n-6)

+ 685799270 a(n-7)

- 909474816 a(n-8)

+ 685799270 a(n-9)

- 295849710 a(n-10)

+ 72968360 a(n-11)

- 10084457 a(n-12)

+ 744035 a(n-13)

- 26224 a(n-14)

+ 335 a(n-15)

- a(n-16)

G.f.: -3x(x^14 -2385x^12 +54940x^11 -451104x^10 +1542340x^9 -2024890x^8 +2024890x^6 -1542340x^5 +451104x^4 -54940x^3 +2385x^2 -1)/ (x^16 -335x^15 +26224x^14 -744035x^13 +10084457x^12 -72968360x^11 +295849710x^10 -685799270x^9 +909474816x^8 -685799270x^7 +295849710x^6 -72968360x^5 +10084457x^4 -744035x^3 +26224x^2 -335x +1).

Crossrefs

Sequence in context: A145231 A318480 A358269 * A024046 A152505 A139301

Adjacent sequences: A167066 A167067 A167068 * A167070 A167071 A167072

Keyword

nonn

Author

Paul Raff

Status

approved