OFFSET
1,2
COMMENTS
Let G_n denote the 3 X n grid graph. G_n has two automorphisms when n = 1, four automorphisms when n = 2, eight automorphisms when n = 3, and four automorphisms when n >= 4.
In the following ~= denotes 'is isomorphic to'.
When n = 1, Aut(G_n) ~= D_2; when n = 2, Aut(G_n) ~= D_4; when n = 3, Aut(G_n) ~= D_8. Here D_n denotes the dihedral group of order n (e.g., D_8 is the symmetry group of a square).
When n = 2 and n >= 4, Aut(G_n) is isomorphic to the Klein four group: Aut(G_n) ~= D_4 ~= V_4 = {e, h, v, r}, consisting of the identity (e), horizontal flip (h), vertical flip (v), and rotation by 180 degrees (r = hv).
When n = 3, a(3) = 28 = A349718(3). If the additional symmetries that occur at n = 3 are disregarded, and we consider only the Klein four-group symmetries, then a(3) = 55.
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Spanning Tree.
Wikipedia, Burnside's lemma.
Index entries for linear recurrences with constant coefficients, signature (18,-63,-144,1060,-1296,-1312,3492,-1312,-1296,1060,-144,-63,18,-1).
FORMULA
a(n) = 18*a(n-1) - 63*a(n-2) - 144*a(n-3) + 1060*a(n-4) - 1296*a(n-5) - 1312*a(n-6) + 3492*a(n-7) - 1312*a(n-8) - 1296*a(n-9) + 1060*a(n-10) - 144*a(n-11) - 63*a(n-12) + 18*a(n-13) - a(n-14) for n > 17.
G.f.: x*(1 - 12*x - 17*x^2 + 647*x^3 - 2104*x^4 - 3777*x^5 + 29040*x^6 - 35295*x^7 - 35423*x^8 + 94304*x^9 - 35415*x^10 - 34995*x^11 + 28620*x^12 - 3888*x^13 - 1701*x^14 + 486*x^15 - 27*x^16)/((1 - 3*x + x^2)*(1 - 15*x + 32*x^2 - 15*x^3 + x^4)*(1 - 15*x^2 + 32*x^4 - 15*x^6 + x^8)).
EXAMPLE
For n = 2, the a(2) = 6 nonequivalent spanning trees are:
+ + + + +---+ +---+ +---+ + +
| | | | | | | | |
+---+ + + +---+ +---+ + + +---+
| | | | | | | | |
+ + +---+ +---+ +---+ +---+ +---+
MATHEMATICA
CoefficientList[Series[(x(1 - 12x - 17x^2 + 647x^3 - 2104x^4 - 3777x^5 + 29040x^6 - 35295x^7 - 35423x^8 + 94304x^9 - 35415x^10 - 34995x^11 + 28620x^12 - 3888x^13 - 1701x^14 + 486x^15 - 27x^16))/((1 - 3x + x^2)(1 - 15x + 32x^2 - 15x^3 + x^4)(1 - 15*x^2 + 32*x^4 - 15x^6 + x^8)), {x, 0, 30}], x]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ariadne Weber-Madison, Aug 07 2026
STATUS
approved