|
Search: id:A007798
|
|
|
| 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
4
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
All 3^n possible starting positions are chosen with equal probability.
|
|
REFERENCES
|
M. A. Alekseyev and T. Berger, On the expected number of random moves to solve the Tower of Hanoi puzzle, Preprint, 2008.
|
|
FORMULA
|
a(n) appears to be the partial sum of A005058(n-1), that is, a(n) = (5^n-2*3^n+1)/4 = 8*a(n-1)-15*a(n-2)+2 [with a(1)=a(0)=0] = 2*A016209(n-2) - Henry Bottomley (se16(AT)btinternet.com), Jun 06 2000
That formula is correct! Indeed, a(n) = (5^n - 2*3^n + 1) / 4. A paper is in preparation. - Max Alekseyev, Feb 04 2008
|
|
CROSSREFS
|
Cf. A134939.
Sequence in context: A038721 A064837 A027433 this_sequence A058052 A119578 A052610
Adjacent sequences: A007795 A007796 A007797 this_sequence A007799 A007800 A007801
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
David G. Poole (dpoole(AT)trentu.ca)
|
|
EXTENSIONS
|
More precise definition and more terms from Max Alekseyev, Feb 04 2008
|
|
|
Search completed in 0.002 seconds
|
