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

16, 12096, 7526400, 4600399104, 2805387952400, 1710196656537600, 1042505162050645904, 635487948490723808256, 387378914569568374118400, 236137288417488262321070400, 143943863916057463999036728976, 87744870926093811441456945561600, 53487256495669025156132129844140944

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}, {1, 5}, {2, 3}, {2, 4}, {3, 4}}. 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) = 735*a(n-1) - 80115*a(n-2) + 2269596*a(n-3) - 23630145*a(n-4) + 89290005*a(n-5) - 139636406*a(n-6) + 89290005*a(n-7) - 23630145*a(n-8) + 2269596*a(n-9) - 80115*a(n-10) + 735*a(n-11) - a(n-12).

G.f.: -16*x*(x^10 + 21*x^9 - 5145*x^8 + 78288*x^7 - 175246*x^6 + 175246*x^4 - 78288*x^3 + 5145*x^2 - 21*x - 1) / (x^12 - 735*x^11 + 80115*x^10 - 2269596*x^9 + 23630145*x^8 - 89290005*x^7 + 139636406*x^6 - 89290005*x^5 + 23630145*x^4 - 2269596*x^3 + 80115*x^2 - 735*x + 1).

Mathematica

CoefficientList[Series[-16 (x^10 + 21 x^9 - 5145 x^8 + 78288 x^7 - 175246 x^6 + 175246 x^4 - 78288 x^3 + 5145 x^2 - 21 x - 1)/(x^12 - 735 x^11 + 80115 x^10 - 2269596 x^9 + 23630145 x^8 - 89290005 x^7 + 139636406 x^6 - 89290005 x^5 + 23630145 x^4 - 2269596 x^3 + 80115 x^2 - 735 x + 1), {x, 0, 12}], x] (* Wesley Ivan Hurt, Jan 15 2024 *)

Crossrefs

Sequence in context: A191945 A290770 A223102 * A233140 A249968 A017188

Adjacent sequences: A167059 A167060 A167061 * A167063 A167064 A167065

Keyword

nonn,easy

Author

Paul Raff

Status

approved