A137889 Number of directed Hamiltonian paths in the n-Hanoi graph.

6, 36, 384, 5460, 84816, 1347396, 21521184, 344194740, 5506552176, 88102619556, 1409633169984, 22554096102420, 360865400232336, 5773845857280516, 92381531540306784, 1478104495968880500, 23649671900884069296, 378394750275931314276, 6054316003862820691584

Offset

1,1

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Andrew Howroyd, Hamiltonian paths in Hanoi graphs

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) = (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

Adjacent sequences: A137886 A137887 A137888 * A137890 A137891 A137892

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 20 2008

Extensions

Terms a(5) and beyond from Andrew Howroyd, Jun 18 2017

Status

approved