|
|
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. 65-79. ISBN 978-0-691-16403-8
|
|
FORMULA
|
a(n) = numerator(e(n)) with e(n) = (3^n-1)*(5^n-3^n) / (2*3^(n-1)), a(n) = (3^n-1)*(5^n-3^n) / 2. - Max Alekseyev, Feb 04 2008
G.f.: -2*x*(45*x^2-1) / ((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)). - 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
|
|
|
|