login
A290004
Wiener index of the n-Hanoi graph.
2
3, 72, 1419, 26580, 487839, 8867088, 160391235, 2894149932, 52158948999, 939440707560, 16915155908523, 304519845578052, 5481780715831215, 98675865000853056, 1776199882077971859, 31971906699808312284, 575497100061532320855, 10358972816581956751128
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
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
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
Sequence in context: A321530 A374898 A062074 * A332188 A071645 A322189
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Sep 03 2017
STATUS
approved