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) 295-303.
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 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
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
AUTHOR
Allan Bickle, Aug 07 2024
EXTENSIONS
More terms from Michel Marcus, Aug 08 2024
STATUS
approved