OFFSET
1,2
COMMENTS
Vertices of the Hanoi graph are configurations of discs on pegs in the Towers of Hanoi puzzle. Edges are a move of a disc from one peg to another.
The shortest path between a pair of vertices u,v may be unique, or there may be 2 different paths. a(n) is the number of vertex pairs with 2 shortest paths. Pairs are ordered, so both u,v and v,u are counted.
For a given vertex u, Hinz et al. characterize and count the destinations v which have 2 shortest paths. Their total x_n is the number of vertex pairs in the graph of n+1 discs. The present sequence is for n discs so a(n) = x_{n-1}.
LINKS
Kevin Ryde, Table of n, a(n) for n = 1..500
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse, and Ciril Petr, Metric Properties of the Tower of Hanoi Graphs and Stern's Diatomic Sequence, European Journal of Combinatorics, volume 26, 2005, pages 693-708. See proposition 3.9.
Index entries for linear recurrences with constant coefficients, signature (8,-17,6).
FORMULA
With P = (5 + sqrt(17))/2 = A082486, and M = (5 - sqrt(17))/2:
a(n) = (3/(4*sqrt(17)))*( (sqrt(17)+1)*P^n - 2*sqrt(17)*3^n + (sqrt(17)-1)*M^n ). [Hinz et al.]
a(n) = (6/sqrt(17)) * Sum_{k=0..n-1} 3^k * (P^(n-1-k) - M^(n-1-k)) [Hinz et al.].
a(n) = 3*a(n-1) + 6*A107839(n-2), paths within and between subgraphs n-1.
a(n) = 8*a(n-1) - 17*a(n-2) + 6*a(n-3).
a(n) = (A052984(n) - 3^n)*3/2.
G.f.: 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x)).
G.f.: (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x).
EXAMPLE
For n=3 discs, the Hanoi graph is
* \
/ \ | top
A---* | subgraph,
/ \ | of n-1 = 2
B * | discs
/ \ / \ |
C---D---E---* /
/ \ two shortest
* * paths for
/ \ / \ A to S
*---* *---* B to T
/ \ / \ C to R
* * R * C to U
/ \ / \ / \ / \ D to S
*---*---*---*---S---T---U---*
Going from the top subgraph down to the bottom right subgraph, there are 5 vertex pairs with two shortest paths. C to R goes around the middle 12-cycle either right or left, and likewise D to S. The other pairs also go each way around the middle. There are 6 ordered pairs of n-1 subgraphs repeating these 5 pairs.
Within the n-1 = 2 disc top subgraph, A and E are in separate n-2 subgraphs (unit triangles) and they are the only pair with two shortest paths. Again 6 combinations of these, and in 3 subgraphs. Total a(3) = 6*5 + 6*3*1 = 48.
PROG
(PARI) my(p=Mod('x, 'x^2-5*'x+2)); a(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Jan 04 2021
STATUS
approved