OFFSET
1,2
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Spanning Tree.
Index entries for linear recurrences with constant coefficients, signature (0,15,0,-32,0,15,0,-1).
FORMULA
G.f.: x*(1 + x)^2*(1 + x - 6*x^2 + x^3 + x^4)/(1 - 15*x^2 + 32*x^4 - 15*x^6 + x^8).
a(n) = 15*a(n-2) - 32*a(n-4) + 15*a(n-6) - a(n-8).
a(n) = A161495(n/2) for even n.
EXAMPLE
For n = 2, a(2) = 3. The three spanning trees of a 3 X 2 grid graph that are fixed under a 180 degree rotation are:
+ + +---+ +---+
| | | |
+---+ +---+ +---+
| | | |
+ + +---+ +---+
MATHEMATICA
LinearRecurrence[{0, 15, 0, -32, 0, 15, 0, -1}, {1, 3, 12, 35, 145, 432, 1807, 5405}, 30]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ariadne Weber-Madison, Aug 07 2026
STATUS
approved