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.