A375256 - OEIS

%I #26 Mar 17 2026 23:46:26

%S 3,12,39,129,453,1677,6429,25149,99453,395517,1577469,6300669,

%T 25184253,100700157,402726909,1610760189,6442745853,25770393597,

%U 103080394749,412319219709,1649272160253,6597079203837,26388297940989,105553154015229,422212540563453,1688850011258877,6755399743045629

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

%C 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.

%C 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.

%H Paolo Xausa, <a href="/A375256/b375256.txt">Table of n, a(n) for n = 1..1000</a>

%H Allan Bickle, <a href="https://allanbickle.wordpress.com/wp-content/uploads/2016/05/sierpinskigraphpaper2-2.pdf">Properties of Sierpinski Triangle Graphs</a>, Springer PROMS 448 (2021), pp. 295-303.

%H Andreas M. Hinz, Sandi Klavžar, and Sara Sabrina Zemljič, <a href="https://doi.org/10.1016/j.dam.2016.09.024">A survey and classification of Sierpinski-type graphs</a>, Discrete Applied Mathematics, Volume 217, Part 3 (2017), pages 565-600.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).

%F a(n) = 3*(2^(2n-3)+3*2^(n-2)-1).

%F a(n) = A370933(n+1) - 3.

%F a(n) = 3*A297928(n-2) for n>=2. - _Alois P. Heinz_, Sep 23 2024

%F From _Elmo R. Oliveira_, Mar 15 2026: (Start)

%F G.f.: 3*x*(1 - 3*x - x^2)/((1 - x)*(1 - 2*x)*(1 - 4*x)).

%F E.g.f.: (1/8)*(3*exp(4*x) + 18*exp(2*x) - 24*exp(x) + 3).

%F a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3) for n >= 4. (End)

%e 2 example graphs:

%e                            o

%e                           / \

%e                          o---o

%e                         /     \

%e              o         o       o

%e             / \       / \     / \

%e            o---o     o---o---o---o

%e Graph:      H_1           H_2

%e Since the level 1 Hanoi graph is a triangle, a(1) = 3.

%t A375256[n_] := 3*(2^(2*n - 3) + 3*2^(n - 2) - 1);

%t Array[A375256, 30] (* or *)

%t LinearRecurrence[{7, -14, 8}, {3, 12, 39}, 30] (* _Paolo Xausa_, Sep 23 2024 *)

%o (PARI) a(n) = 3*(2^(2*n-3)+3*2^(n-2)-1); \\ _Michel Marcus_, Aug 08 2024

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

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

%Y Cf. A193233, A297928.

%K nonn,easy

%O 1,1

%A _Allan Bickle_, Aug 07 2024

%E More terms from _Michel Marcus_, Aug 08 2024