OFFSET
1,1
COMMENTS
A level 1 Hanoi graph is a triangle. Level n+1 is formed from three copies of level n by adding edges between pairs of corner vertices of each pair of triangles. This graph represents the allowable moves in the Towers of Hanoi problem with n disks.
Antipodal vertices are a pair of vertices at maximum distance in a graph. The diameter of the level n Hanoi graph is 2^n - 1.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..1000
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021), pp. 295-303.
Andreas M. Hinz, Sandi Klavžar, and Sara Sabrina Zemljič, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics, Volume 217, Part 3 (2017), pages 565-600.
Eric Weisstein's World of Mathematics, Hanoi Graph.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).
FORMULA
a(n) = 3*(2^(2n-3)+3*2^(n-2)-1).
a(n) = A370933(n+1) - 3.
a(n) = 3*A297928(n-2) for n>=2. - Alois P. Heinz, Sep 23 2024
From Elmo R. Oliveira, Mar 15 2026: (Start)
G.f.: 3*x*(1 - 3*x - x^2)/((1 - x)*(1 - 2*x)*(1 - 4*x)).
E.g.f.: (1/8)*(3*exp(4*x) + 18*exp(2*x) - 24*exp(x) + 3).
a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3) for n >= 4. (End)
EXAMPLE
2 example graphs:
o
/ \
o---o
/ \
o o o
/ \ / \ / \
o---o o---o---o---o
Graph: H_1 H_2
Since the level 1 Hanoi graph is a triangle, a(1) = 3.
MATHEMATICA
A375256[n_] := 3*(2^(2*n - 3) + 3*2^(n - 2) - 1);
Array[A375256, 30] (* or *)
LinearRecurrence[{7, -14, 8}, {3, 12, 39}, 30] (* Paolo Xausa, Sep 23 2024 *)
PROG
(PARI) a(n) = 3*(2^(2*n-3)+3*2^(n-2)-1); \\ Michel Marcus, Aug 08 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Allan Bickle, Aug 07 2024
EXTENSIONS
More terms from Michel Marcus, Aug 08 2024
STATUS
approved