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

Author

Allan Bickle, Aug 07 2024

Keywords

• nonn

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.

Examples

			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.
		

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

Crossrefs

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

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

Cf. A193233, A297928.

Programs

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

PARI

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

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

Extensions

More terms from Michel Marcus, Aug 08 2024