login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; graph; refs; listen; history; text; internal format)
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).

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. - Conjectured by Henry Bottomley, Jun 06 2000, proved by Max Alekseyev, Feb 04 2008

a(n) = 9*a(n-1)-23*a(n-2)+15*a(n-3). G.f.: -2*x^2 / ((x-1)*(3*x-1)*(5*x-1)). - Colin Barker, Sep 17 2014

PROG

(MAGMA) [(5^n-2*3^n+1)/4: n in [1..25]]; // Vincenzo Librandi, Oct 11 2011

(PARI) concat([0, 0], Vec(-2*x^2/((x-1)*(3*x-1)*(5*x-1)) + O(x^100))) \\ Colin Barker, Sep 17 2014

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 21 19:25 EDT 2019. Contains 325199 sequences. (Running on oeis4.)