Lucas Bang - cp's OEIS frontend

User: Lucas Bang

Lucas Bang has authored 1 sequences.

A363165 The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.

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

Mithra Karamchedu and Lucas Bang, Jul 06 2023

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.

			For n = 3, the a(3) = 6 nonequivalent spanning trees are:
+   +   +---+   +---+   +   +   +   +   +---+
|   |   |       |       |   |   |   |   |
+---+   +---+   +---+   +---+   +   +   +   +
    |   |           |   |   |   |   |   |   |
+---+   +---+   +---+   +   +   +---+   +---+

Mithra Karamchedu, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Ladder Graph.
Index entries for linear recurrences with constant coefficients, signature (6,-6,-18,38,-18,-6,6,-1).

Cf. A001353, A001835, A048788.

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])]]]

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

cp's OEIS Frontend

User: Lucas Bang

A363165 The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula