|
%I #39 Sep 08 2022 08:44:35
%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#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (9,-23,15).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%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. - _Henry Bottomley_, Jun 06 2000, proved by _Max Alekseyev_, Feb 04 2008
%F From _Colin Barker_, Sep 17 2014: (Start)
%F a(n) = 9*a(n-1) - 23*a(n-2) + 15*a(n-3).
%F G.f.: 2*x^2/((1-x)*(1-3*x)*(1-5*x)). (End)
%F E.g.f.: (exp(x) - 2*exp(3*x) + exp(5*x))/4. - _G. C. Greubel_, Mar 05 2020
%p seq( (1 -2*3^n +5^n)/4, n=0..25); # _G. C. Greubel_, Mar 05 2020
%t Table[(1 -2*3^n +5^n)/4, {n,0,25}] (* _G. C. Greubel_, Mar 05 2020 *)
%o (Magma) [(5^n-2*3^n+1)/4: n in [0..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^30))) \\ _Colin Barker_, Sep 17 2014
%o (Sage) [(1 -2*3^n +5^n)/4 for n in (0..25)] # _G. C. Greubel_, Mar 05 2020
%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
| 