A007798 Expected number of random moves in Tower of Hanoi problem with n disks starting with a randomly chosen position and ending at a position with all disks on the same peg.

0, 0, 2, 18, 116, 660, 3542, 18438, 94376, 478440, 2411882, 12118458, 60769436, 304378620, 1523487422, 7622220078, 38125449296, 190670293200, 953480606162, 4767790451298, 23840114517956, 119204059374180, 596030757224102, 2980185167180118, 14901019979079416

Offset

0,3

Comments

All 3^n possible starting positions are chosen with equal probability.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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 (9,-23,15).

Index entries for sequences related to Towers of Hanoi

Formula

For n>1, a(n) = 8*a(n-1) - 15*a(n-2) + 2 = 2*A016209(n-2). - Henry Bottomley, Jun 06 2000

a(n) = (5^n - 2*3^n + 1) / 4. - Henry Bottomley, Jun 06 2000, proved by Max Alekseyev, Feb 04 2008

From Colin Barker, Sep 17 2014: (Start)

a(n) = 9*a(n-1) - 23*a(n-2) + 15*a(n-3).

G.f.: 2*x^2/((1-x)*(1-3*x)*(1-5*x)). (End)

E.g.f.: (exp(x) - 2*exp(3*x) + exp(5*x))/4. - G. C. Greubel, Mar 05 2020

Maple

seq( (1 -2*3^n +5^n)/4, n=0..25); # G. C. Greubel, Mar 05 2020

Mathematica

Table[(1 -2*3^n +5^n)/4, {n, 0, 25}] (* G. C. Greubel, Mar 05 2020 *)

Prog

(Magma) [(5^n-2*3^n+1)/4: n in [0..25]]; // Vincenzo Librandi, Oct 11 2011
(PARI) concat([0, 0], Vec(-2*x^2/((x-1)*(3*x-1)*(5*x-1)) + O(x^30))) \\ Colin Barker, Sep 17 2014
(Sage) [(1 -2*3^n +5^n)/4 for n in (0..25)] # G. C. Greubel, Mar 05 2020

Crossrefs

Partial sums of A005058.

Cf. A134939.

Sequence in context: A224902 A027433 A153338 * A058052 A119578 A052610

Adjacent sequences: A007795 A007796 A007797 * A007799 A007800 A007801

Keyword

nonn,easy

Author

David G. Poole (dpoole(AT)trentu.ca)

Extensions

More precise definition and more terms from Max Alekseyev, Feb 04 2008

a(0)=0 prepended by Max Alekseyev, Sep 08 2014

Status

approved