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
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
Programs
-
Magma
[(5^n-2*3^n+1)/4: n in [0..25]]; // Vincenzo Librandi, Oct 11 2011
-
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 *) -
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
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
Extensions
More precise definition and more terms from Max Alekseyev, Feb 04 2008
a(0)=0 prepended by Max Alekseyev, Sep 08 2014
Comments