login
A137889
Number of directed Hamiltonian paths in the n-Hanoi graph.
10
6, 36, 384, 5460, 84816, 1347396, 21521184, 344194740, 5506552176, 88102619556, 1409633169984, 22554096102420, 360865400232336, 5773845857280516, 92381531540306784, 1478104495968880500, 23649671900884069296, 378394750275931314276, 6054316003862820691584
OFFSET
1,1
LINKS
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hanoi Graph
FORMULA
a(n) = (208 + 16*3^(n + 2) + 13*4^(n + 2) + 25*16^n)/312. - Eric W. Weisstein, Jun 19 2017
a(n) = 3*a(n-1) + (25*16^n + 64*4^n - 512)/384 for n > 1. - Andrew Howroyd, Jun 18 2017
From Colin Barker, Jul 30 2017: (Start)
G.f.: 6*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.
(End)
MATHEMATICA
Table[(208 + 16 3^(n + 2) + 13 4^(n + 2) + 25 16^n)/312, {n, 10}] (* Eric W. Weisstein, Jun 19 2017 *)
RecurrenceTable[{a[1] == 6, a[n] == 3 a[n - 1] + (25 16^n + 64 4^n - 512)/384}, a, {n, 10}] (* Eric W. Weisstein, Jun 19 2017 *)
PROG
(PARI) a(n)=if(n==1, 6, 3*a(n-1) + (25*16^n + 64*4^n - 512)/384); \\ Andrew Howroyd, Jun 18 2017
(PARI) Vec(6*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)) + O(x^30)) \\ Colin Barker, Jul 30 2017
CROSSREFS
Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).
Sequence in context: A229530 A265474 A277474 * A071555 A080491 A077704
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Feb 20 2008
EXTENSIONS
Terms a(5) and beyond from Andrew Howroyd, Jun 18 2017
STATUS
approved