|
|
A060590
|
|
Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.
|
|
4
|
|
|
0, 2, 2, 14, 10, 62, 42, 254, 170, 1022, 682, 4094, 2730, 16382, 10922, 65534, 43690, 262142, 174762, 1048574, 699050, 4194302, 2796202, 16777214, 11184810, 67108862, 44739242, 268435454, 178956970, 1073741822, 715827882, 4294967294
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*(2^n - 1)*(2 - (-1)^n)/3.
G.f.: (4*x^3+2*x^2+2*x)/(4*x^4-5*x^2+1).
a(n+4) = 5*a(n+2) - 4*a(n). (End)
|
|
EXAMPLE
|
a(2)=2 since there are nine equally likely possibilities, with times required of 0,1,1,2,2,3,3,3,3 giving an average of 18/9 = 2/1.
|
|
PROG
|
(PARI) a(n)={2*(2^n - 1)*(2 - (-1)^n)/3} \\ Harry J. Smith, Jul 07 2009
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,frac,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|