|
| |
|
|
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.
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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.
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 1..1000
|
|
|
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
|
|
|
PROG
| (MAGMA) [(5^n-2*3^n+1)/4: n in [1..25]]; // Vincenzo Librandi, Oct 11 2011
|
|
|
CROSSREFS
| Cf. A134939.
Sequence in context: A064837 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
|
| |
|
|
