Number of Hamilton paths in the Hanoi graph of order n. ======================================================= Hanoi graph of order 2. A o / \ o---o / \ o o / \ / \ o---o---o---o B C Define G_n = the Hanoi graph of order n. a(n) = number of directed hamilton paths in G_n. b(n) = number of hamilton paths in G_n which start at vertex A. c(n) = number of paths in G_n which starts at vertex A such that remainder is a path from B to C. d(n) = number of paths in G_n which start at vertex B such that remainder is a path starting at vertex C. e(n) = number of hamilton paths in G_n which start at vertex A and end at vertex B. Case analysis for e(n): [Paths from A to B] A o / o---o \ o o / \ \ o o---o---o B e.e.e C e(1) = 1. e(n+1) = e(n)*e(n)*e(n). By induction e(n)=1. Case analysis for b(n): [Paths starting at A] A A o o \ / o---o o o / / \ o o o o / / \ o---o---o o o---o---o---o B e.e.b C B c.e.e C b(1) = 2. b(n+1) = 2*b(n) + 2*c(n). Case analysis for c(n): [Path starting at A + path from B to C] A A A o o o \ o o o---o o---o / / \ o o o o o o / \ / \ / \ \ / o o---o o o---o---o o o---o o---o B b.e.e C B e.c.e C B c.e.e C c(1) = 1. c(n+1) = b(n) + 2*c(n) + c(n) = b(n) + 3*c(n). Case analysis for d(n): [Paths starting at both B and C] A A A A o o o o o o o o o o o o \ \ / / \ o o o o o o o o / / \ \ \ / \ \ / o o o---o o o---o o o o---o o o---o o---o B b.b.e C B b.e.c C B b.c.e C B d.e.e A A A A o o o o / \ / \ / \ / \ o o o o o o o o / \ / \ / \ / \ o o o o o o o o \ \ \ \ / o o---o---o o o---o o o---o---o o o o o---o B e.c.c C B e.c.c C B e.c.c C B e.d.e C d(1) = 2. d(n+1) = (2*b(n)^2 + 2*b(n)*c(n) + 2*b(n)*c(n) + d(n)) + (2*c(n)^2 + 2*c(n)^2 + 2*c(n)^2 + 2*d(n)) = 2*b(n)^2 + 4*b(n)*c(n) + 6*c(n)^2 + 3*d(n). Case analysis for a(n) [Dircected hamilton paths] Either path has ends in two different subtriangles or both ends are in the same subtriangle. A A o o / \ o o o o / \ / \ o o o o / \ o o o o o---o---o---o B e.b.b C B d.e.e C a(1) = 6. a(n+1) = 6*b(n)^2 + 6*d(n). Formula ------- b(1)-c(1) = 2 - 1 = 1. b(n+1) - c(n+1) = (2*b(n)+2*c(n)) - (b(n)+3*c(n)) = b(n) - c(n). By induction b(n)-c(n) = 1.. b(n) = (4^n + 2)/3. c(n) = (4^n - 1)/3. a(n) = 3*a(n-1) + (25*16^n + 64*4^n - 512)/384 for n > 1.