%I #48 Jul 11 2023 11:17:55
%S 1,1,6,17,59,204,750,2746,10215,37936,141468,527283,1967449,7340090,
%T 27392124,102219380,381482477,1423676862,5313214098,19829053909,
%U 74002960983,276182321224,1030726172586,3846720619566,14356155740947,53577895814828,199955425410792
%N The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.
%C The ladder graph L_n is the 2 X n grid graph.
%C L_n has two automorphisms when n = 1, eight automorphisms when n = 2, and four automorphisms when n >= 3.
%C 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.
%H Mithra Karamchedu, <a href="/A363165/b363165.txt">Table of n, a(n) for n = 1..1000</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>.
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (6,-6,-18,38,-18,-6,6,-1).
%F a(1) = 1, a(2) = 1, for n >= 3:
%F a(n) = A001353(n)/4 + A048788(n)/2 + n/4, for n odd, and
%F a(n) = A001353(n)/4 + A001353(n/2)/2 + n/4, for n even.
%F For n >= 3, a closed form is:
%F 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
%F 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.
%F 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
%F 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
%e For n = 3, the a(3) = 6 nonequivalent spanning trees are:
%e + + +---+ +---+ + + + + +---+
%e | | | | | | | | |
%e +---+ +---+ +---+ +---+ + + + +
%e | | | | | | | | |
%e +---+ +---+ +---+ + + +---+ +---+
%t 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])]]]
%Y Cf. A001353, A001835, A048788.
%K nonn,easy
%O 1,3
%A _Mithra Karamchedu_ and _Lucas Bang_, Jul 06 2023