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

%I

%S 0,0,2,18,116,660,3542,18438,94376,478440,2411882,12118458,60769436,

%T 304378620,1523487422,7622220078,38125449296,190670293200,

%U 953480606162,4767790451298,23840114517956,119204059374180,596030757224102,2980185167180118,14901019979079416

%N 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.

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

%H Vincenzo Librandi, <a href="/A007798/b007798.txt">Table of n, a(n) for n = 0..1000</a>

%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 <a href="/index/Rec">Index entries for linear recurrences with constant coefficients</a>, signature (9,-23,15).

%F For n>1, a(n) = 8*a(n-1) - 15*a(n-2) + 2 = 2*A016209(n-2). - _Henry Bottomley_, Jun 06 2000

%F a(n) = (5^n - 2*3^n + 1) / 4. - Conjectured by _Henry Bottomley_, Jun 06 2000, proved by _Max Alekseyev_, Feb 04 2008

%F 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

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

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

%Y Partial sums of A005058.

%Y Cf. A134939.

%K nonn,easy

%O 0,3

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

%E More precise definition and more terms from _Max Alekseyev_, Feb 04 2008

%E a(0)=0 prepended by _Max Alekseyev_, Sep 08 2014

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 August 23 00:59 EDT 2019. Contains 326211 sequences. (Running on oeis4.)