OFFSET
1,1
COMMENTS
Sequence gives 1/2 of the total number of moves summed over all starting and finishing positions in the tower of Hanoi puzzle with n disks. For just the total number of moves from all starting positions to the standard finish position see A060589.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..100
T. Chan, A statistical analysis of the towers of Hanoi problem, Internat. J. Comput. Math. 28: 57-65.
A. Hinz, The Tower of Hanoi, L'Enseignement Mathématique, 35: 289-321.
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Wiener Index
Wikipedia, Tower of Hanoi
Index entries for linear recurrences with constant coefficients, signature (35, -395, 1761, -2916, 972).
FORMULA
a(n) = 35*a(n-1) - 395*a(n-2) + 1761*a(n-3) - 2916*a(n-4) + 972*a(n-5).
G.f.: 3*x*(1 - 11*x + 28*x^2 + 24*x^3)/((1 - 3*x)*(1 - 9*x)*(1 - 18*x)*(1 - 5*x + 2*x^2)). [Corrected by Georg Fischer, May 19 2019]
MATHEMATICA
(* Start from Eric W. Weisstein, Sep 07 2017 *)
Table[3/1003 2^-n ((34 - 3 Sqrt[17]) (5 - Sqrt[17])^n + (5 + Sqrt[17])^n (34 + 3 Sqrt[17])) - 3^(n + 1)/10 + 9^n (233/885 2^n - 1/6), {n, 10}]
LinearRecurrence[{35, -395, 1761, -2916, 972}, {3, 72, 1419, 26580, 487839}, 20]
CoefficientList[Series[(3 (1 - 11 x + 28 x^2 + 24 x^3))/((1 - 3 x) (1 - 9 x) (1 - 18 x) (1 - 5 x + 2 x^2)), {x, 0, 20}], x]
(* End *)
PROG
(PARI) Vec(3*(1 - 11*x + 28*x^2 + 24*x^3)/((1 - 3*x)*(1 - 9*x)*(1 - 18*x)*(1 - 5*x + 2*x^2)) + O(x^20))
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Sep 03 2017
STATUS
approved