A308134 Number of (undirected) Hamiltonian paths in the n-Hanoi graph.

3, 18, 192, 2730, 42408, 673698, 10760592, 172097370, 2753276088, 44051309778, 704816584992, 11277048051210, 180432700116168, 2886922928640258, 46190765770153392, 739052247984440250, 11824835950442034648, 189197375137965657138, 3027158001931410345792

Offset

1,1

Links

Colin Barker, Table of n, a(n) for n = 1..800

Eric Weisstein's World of Mathematics, Hamiltonian Path

Eric Weisstein's World of Mathematics, Hanoi Graph

Index entries for linear recurrences with constant coefficients, signature (24,-147,316,-192).

Formula

a(n) = A137889(n)/2.

From Colin Barker, Jul 19 2019: (Start)

G.f.: 3*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)).

a(n) = 24*a(n-1) - 147*a(n-2) + 316*a(n-3) - 192*a(n-4) for n>4.

a(n) = (208 + 16*3^(2+n) + 13*4^(2+n) + 25*16^n) / 624.

(End)

Prog

(PARI) Vec(3*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)) + O(x^20)) \\ Colin Barker, Jul 19 2019

Crossrefs

Cf. A137889.

Sequence in context: A363414 A002824 A259336 * A160707 A330764 A367487

Adjacent sequences: A308131 A308132 A308133 * A308135 A308136 A308137

Keyword

nonn,easy

Author

Eric W. Weisstein, May 14 2019

Status

approved