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, 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

Table of n, a(n) for n=0..20.

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

Index entries for linear recurrences with constant coefficients, signature (32,-342,1440,-2025).

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

Cf. A007798, A134939, A226511.

Sequence in context: A041629 A278845 A159197 * A331868 A180375 A160470

Adjacent sequences: A246958 A246959 A246960 * A246962 A246963 A246964

Keyword

nonn,easy

Author

Max Alekseyev, Sep 08 2014

Status

approved