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

1, 201, 27872, 3656793, 474581525, 61445719296, 7951276371389, 1028790034978377, 133107787044919648, 17221739109190982025, 2228177484370996025801, 288285215706960759705600, 37298804748402271018820409, 4825779209505263485071458889

Offset

1,2

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}}. 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) = 201 a(n-1)

- 11104 a(n-2)

+ 259893 a(n-3)

- 3001225 a(n-4)

+ 18824856 a(n-5)

- 67848270 a(n-6)

+ 144802410 a(n-7)

- 186068896 a(n-8)

+ 144802410 a(n-9)

- 67848270 a(n-10)

+ 18824856 a(n-11)

- 3001225 a(n-12)

+ 259893 a(n-13)

- 11104 a(n-14)

+ 201 a(n-15)

- a(n-16)

G.f.: -x(x^14 -1425x^12 +26532x^11 -180448x^10 +545916x^9 -661242x^8 +661242x^6 -545916x^5 +180448x^4 -26532x^3 +1425x^2 -1)/ (x^16 -201x^15 +11104x^14 -259893x^13 +3001225x^12 -18824856x^11 +67848270x^10 -144802410x^9 +186068896x^8 -144802410x^7 +67848270x^6 -18824856x^5 +3001225x^4 -259893x^3 +11104x^2 -201x +1).

Crossrefs

Sequence in context: A371109 A371057 A305724 * A175188 A227152 A210166

Adjacent sequences: A167067 A167068 A167069 * A167071 A167072 A167073

Keyword

nonn

Author

Paul Raff

Status

approved