login
A246961
Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting at a randomly chosen valid configuration and ending with all disks at peg 1.
0
0, 4, 146, 3034, 52916, 857824, 13426406, 206324374, 3138660776, 47471139964, 715573119866, 10765074628114, 161759034582236, 2428929817996504, 36456836245518926, 547058495778290254, 8207730761823753296, 123132640134289171444, 1847139704277091999586, 27708446454015214334794, 415638854666404701309956
OFFSET
0,2
COMMENTS
The expected number of random moves is given by a(n)/3^n = a(n)/A000244(n).
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) = ( (3^n - 1)*(5^(n+1) - 2*3^(n+1)) + 5^n - 3^n ) / 4.
a(n) = 3^n*A007798(n) + 2*A134939(n).
G.f.: -2*x*(135*x^2-9*x-2) / ((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)). - Colin Barker, Sep 17 2014
PROG
(PARI) concat(0, Vec(-2*x*(135*x^2-9*x-2)/((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)) + O(x^100))) \\ Colin Barker, Sep 17 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Max Alekseyev, Sep 08 2014
STATUS
approved