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.

0, 2, 64, 1274, 21760, 348722, 5422144, 83000234, 1259729920, 19027002722, 286576949824, 4309163074394, 64731832372480, 971825991711122, 14585021567101504, 218843984372767754, 3283277591489597440, 49254723695591689922, 738870890792896773184, 11083513664870504400314

Offset: 0

Author

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

Keywords

• nonn
• frac
• easy

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.

Examples

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

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
• mersenneforum.org, Towers of Hanoi with random moves.
• Index entries for linear recurrences with constant coefficients, signature (32,-342,1440,-2025).
• Index entries for sequences related to Towers of Hanoi

Crossrefs

Cf. A007798, A134940.

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

Extensions

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

Shorter name by Michel Marcus, Dec 27 2012