login
A363165
The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.
1
1, 1, 6, 17, 59, 204, 750, 2746, 10215, 37936, 141468, 527283, 1967449, 7340090, 27392124, 102219380, 381482477, 1423676862, 5313214098, 19829053909, 74002960983, 276182321224, 1030726172586, 3846720619566, 14356155740947, 53577895814828, 199955425410792
OFFSET
1,3
COMMENTS
The ladder graph L_n is the 2 X n grid graph.
L_n has two automorphisms when n = 1, eight automorphisms when n = 2, and four automorphisms when n >= 3.
When n = 1, Aut(L_n) = D_2; when n = 2, Aut(L_n) = D_8 (D_n is the dihedral group of order n). When n >= 3, Aut(L_n) = {e, h, v, r}, consisting of the identity (e), horizontal flip (h), vertical flip (v), and rotation (r = hv). For n >= 3, Aut(L_n) is isomorphic to the Klein four-group.
LINKS
Eric Weisstein's World of Mathematics, Ladder Graph.
FORMULA
a(1) = 1, a(2) = 1, for n >= 3:
a(n) = A001353(n)/4 + A048788(n)/2 + n/4, for n odd, and
a(n) = A001353(n)/4 + A001353(n/2)/2 + n/4, for n even.
For n >= 3, a closed form is:
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(8*sqrt(3)) + ((2 + sqrt(3))^(n/2) + (2 - sqrt(3))^(n/2))/(2*sqrt(6)) + n/4, for n odd, and
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(8*sqrt(3)) + ((2 + sqrt(3))^(n/2) - (2 - sqrt(3))^(n/2))/(4*sqrt(3)) + n/4, for n even.
a(n) = 6*a(n-1) - 6*a(n-2) - 18*a(n-3) + 38*a(n-4) - 18*a(n-5) - 6*a(n-6) + 6*a(n-7) - a(n-8) for n > 10. - Peter Kagey, Jul 08 2023
G.f.: x*(1 - 5*x + 6*x^2 + 5*x^3 - 27*x^4 + 40*x^5 - 18*x^6 - 6*x^7 + 6*x^8 - x^9)/((1 - x)^2*(1 - 4*x + x^2)*(1 - 4*x^2 + x^4)). - Stefano Spezia, Jul 09 2023
EXAMPLE
For n = 3, the a(3) = 6 nonequivalent spanning trees are:
+ + +---+ +---+ + + + + +---+
| | | | | | | | |
+---+ +---+ +---+ +---+ + + + +
| | | | | | | | |
+---+ +---+ +---+ + + +---+ +---+
MATHEMATICA
a[n_] := If[n == 1 || n == 2, 1, FullSimplify[n/4 + ((2 + Sqrt[3])^n - (2 -Sqrt[3])^n)/(8*Sqrt[3]) + If [OddQ[n], ((2 + Sqrt[3])^(n/2) + (2 - Sqrt[3])^(n/2))/(2*Sqrt[6]), ((2 + Sqrt[3])^(n/2) - (2 - Sqrt[3])^(n/2))/(4*Sqrt[3])]]]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Mithra Karamchedu and Lucas Bang, Jul 06 2023
STATUS
approved