

A134939


Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting on peg 1 and ending on peg 3.


3



0, 2, 64, 1274, 21760, 348722, 5422144, 83000234, 1259729920, 19027002722, 286576949824, 4309163074394, 64731832372480, 971825991711122, 14585021567101504, 218843984372767754, 3283277591489597440, 49254723695591689922, 738870890792896773184, 11083513664870504400314
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Both allowable transitions out of any of the three special states in which all the disks are on one of the pegs have probability 1/2 and each of the three allowable transitions out of any of the other 3^n  3 states have probability 1/3.


LINKS

M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 6579. ISBN 9780691164038


FORMULA

a(n) = numerator(e(n)) with e(n) = (3^n1)*(5^n3^n) / (2*3^(n1)), a(n) = (3^n1)*(5^n3^n) / 2.  Max Alekseyev, Feb 04 2008
G.f.: 2*x*(45*x^21) / ((3*x1)*(5*x1)*(9*x1)*(15*x1)).  Colin Barker, Dec 26 2012


EXAMPLE

The values of e(0), ..., e(4), e(5) are 0, 2, 64/3, 1274/9, 21760/27, 348722/81.


CROSSREFS



KEYWORD

nonn,frac,easy


AUTHOR

Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008


EXTENSIONS

Values of e(5) onwards and general formula found by Max Alekseyev, Feb 02 2008, Feb 04 2008


STATUS

approved



