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

Author

Eric W. Weisstein, May 14 2019

Keywords

• nonn
• easy

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

Crossrefs

Cf. A137889.

Programs

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

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)