A290004 Wiener index of the n-Hanoi graph.

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

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).

Index entries for sequences related to Towers 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

Cf. A060589, A290129.

Sequence in context: A089537 A321530 A062074 * A332188 A071645 A322189

Adjacent sequences: A290001 A290002 A290003 * A290005 A290006 A290007

Keyword

nonn,easy

Author

Andrew Howroyd, Sep 03 2017

Status

approved