|
Search: id:A134939
|
|
|
| A134939 |
|
Consider a 3-peg Tower of Hanoi configuration which begins with n disks on peg 1. Moves are made at random, where the 1-step transition probabilities out of any state are equal. Let e(n) be the expected number of transitions to reach the state in which which all disks are on peg 3. Sequence gives a(n), the numerator of e(n). |
|
+0
3
|
|
| 0, 2, 64, 1274, 21760, 348722, 5422144, 83000234, 1259729920, 19027002722, 286576949824, 4309163074394, 64731832372480, 971825991711122, 14585021567101504, 218843984372767754, 3283277591489597440, 49254723695591689922, 738870890792896773184, 11083513664870504400314
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
Both allowable transitions out of any of the three special states in which all the disks are on one of the pegs have probabilty 1/2, and each of the three allowable transitions out of any of the other 3^n - 3 states have probabilty 1/3.
|
|
REFERENCES
|
M. A. Alekseyev and T. Berger, On the expected number of random moves to solve the Tower of Hanoi puzzle, Preprint, 2008.
|
|
FORMULA
|
e(n) = (3^n-1)*(5^n-3^n) / (2*3^(n-1)), a(n) = (3^n-1)*(5^n-3^n) / 2. A paper is in preparation. - Max Alekseyev, Feb 04 2008
|
|
EXAMPLE
|
The values of e(0), ..., e(4), e(5) are 0, 2, 64/3, 1274/9, 21760/27, 348722/81.
|
|
CROSSREFS
|
Cf. A134940.
Adjacent sequences: A134936 A134937 A134938 this_sequence A134940 A134941 A134942
Sequence in context: A120829 A120121 A047707 this_sequence A122603 A127691 A013822
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008
|
|
EXTENSIONS
|
Values of e(5) onwards and general formula found by Max Alekseyev (maxale(AT)gmail.com), Feb 02 2008, Feb 04 2008
|
|
|
Search completed in 0.002 seconds
|
