A291876 - OEIS

A291876

Consider the graph with one central vertex connected to three outer vertices (a star graph). Then, a(n) is the minimum number of moves required to transfer a stack of n pegs from one outer vertex to another outer vertex, moving pegs to adjacent vertices, following the rules of the Towers of Hanoi.

2, 6, 12, 20, 32, 48, 66, 90, 122, 158, 206, 260, 324, 396, 492, 600, 728, 872, 1034, 1226, 1442, 1698, 1986, 2310, 2694, 3126, 3612, 4124, 4700, 5348, 6116, 6980, 7952, 8976, 10128, 11424, 12882, 14418, 16146, 18090, 20138, 22442, 25034, 27950, 31022, 34478, 38366

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

Thierry Bousch, La Tour de Stockmeyer, Séminaire Lotharingien de Combinatoire 77 (2017), Article B77d.

Caroline Holz auf der Heide, Distances and automatic sequences in distinguished variants of Hanoi graphs, Dissertation. Fakultät für Mathematik, Informatik und Statistik. Ludwig-Maximilians-Universität München, 2016. [See Chapter 3.]

Paul K. Stockmeyer, Variations on the Four-Post Tower of Hanoi Puzzle, Congr. Numer., 102 (1994), pp. 3-12.

Eric Weisstein's World of Mathematics, Star Graph

Index entries for sequences related to Towers of Hanoi

FORMULA

Conjecturally, a(n) = 2*A259823(n).

This conjecture was proved by Thierry Bousch, see link. - Paul Zimmermann, Oct 05 2015

MAPLE

A[0]:= 0:

A[1]:= 2:

for n from 2 to 100 do A[n]:= min(seq(3*A[k]+2^(n-k+1)-2, k=0..n-1)) od:

seq(A[i], i=1..100); # Robert Israel, Oct 27 2017

CROSSREFS