A375256 Number of pairs of antipodal vertices in the level n Hanoi graph.

3, 12, 39, 129, 453, 1677, 6429, 25149, 99453, 395517, 1577469, 6300669, 25184253, 100700157, 402726909, 1610760189, 6442745853, 25770393597, 103080394749, 412319219709, 1649272160253, 6597079203837, 26388297940989, 105553154015229, 422212540563453, 1688850011258877, 6755399743045629

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

Table of n, a(n) for n=1..27.

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.

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.

Prog

(PARI) a(n) = 3*(2^(2*n-3)+3*2^(n-2)-1); \\ Michel Marcus, Aug 08 2024

Crossrefs

Cf. A000225, A029858, A058809 (Hanoi graphs).

Cf. A370933 (antipodal pairs in Sierpiński triangle graphs).

Sequence in context: A240806 A242587 A330169 * A373629 A290906 A110153

Adjacent sequences: A375252 A375253 A375255 * A375257 A375258 A375259

Keyword

nonn

Author

Allan Bickle, Aug 07 2024

Extensions

More terms from Michel Marcus, Aug 08 2024

Status

approved