%I #30 Apr 08 2024 06:56:11
%S 0,2,64,1274,21760,348722,5422144,83000234,1259729920,19027002722,
%T 286576949824,4309163074394,64731832372480,971825991711122,
%U 14585021567101504,218843984372767754,3283277591489597440,49254723695591689922,738870890792896773184,11083513664870504400314
%N 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.
%C 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.
%H M. A. Alekseyev and T. Berger, <a href="http://arxiv.org/abs/1304.3780">Solving the Tower of Hanoi with Random Moves</a>. 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
%H mersenneforum.org, <a href="http://www.mersenneforum.org/showthread.php?t=9960">Towers of Hanoi with random moves</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (32,-342,1440,-2025).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F 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
%F 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
%e The values of e(0), ..., e(4), e(5) are 0, 2, 64/3, 1274/9, 21760/27, 348722/81.
%Y Cf. A007798, A134940.
%K nonn,frac,easy
%O 0,2
%A Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008
%E Values of e(5) onwards and general formula found by _Max Alekseyev_, Feb 02 2008, Feb 04 2008
%E Shorter name by _Michel Marcus_, Dec 27 2012