%I #12 Jan 14 2021 02:36:07
%S 0,6,48,282,1476,7302,35016,164850,767340,3546366,16315248,74837802,
%T 342621396,1566620022,7157423256,32682574050,149184117180,
%U 680813718126,3106475197248,14173073072922,64659388538916,294971717255142,1345602571317096,6138257708432850
%N Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).
%C 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.
%C 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.
%C 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}.
%H Kevin Ryde, <a href="/A340309/b340309.txt">Table of n, a(n) for n = 1..500</a>
%H Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse, and Ciril Petr, <a href="https://doi.org/10.1016/j.ejc.2004.04.009">Metric Properties of the Tower of Hanoi Graphs and Stern's Diatomic Sequence</a>, European Journal of Combinatorics, volume 26, 2005, pages 693-708. See proposition 3.9.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (8,-17,6).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F With P = (5 + sqrt(17))/2 = A082486, and M = (5 - sqrt(17))/2:
%F a(n) = (3/(4*sqrt(17)))*( (sqrt(17)+1)*P^n - 2*sqrt(17)*3^n + (sqrt(17)-1)*M^n ). [Hinz et al.]
%F a(n) = (6/sqrt(17)) * Sum_{k=0..n-1} 3^k * (P^(n-1-k) - M^(n-1-k)) [Hinz et al.].
%F a(n) = 3*a(n-1) + 6*A107839(n-2), paths within and between subgraphs n-1.
%F a(n) = 8*a(n-1) - 17*a(n-2) + 6*a(n-3).
%F a(n) = (A052984(n) - 3^n)*3/2.
%F G.f.: 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x)).
%F G.f.: (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x).
%e For n=3 discs, the Hanoi graph is
%e * \
%e / \ | top
%e A---* | subgraph,
%e / \ | of n-1 = 2
%e B * | discs
%e / \ / \ |
%e C---D---E---* /
%e / \ two shortest
%e * * paths for
%e / \ / \ A to S
%e *---* *---* B to T
%e / \ / \ C to R
%e * * R * C to U
%e / \ / \ / \ / \ D to S
%e *---*---*---*---S---T---U---*
%e 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.
%e 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.
%o (PARI) my(p=Mod('x, 'x^2-5*'x+2)); a(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;
%Y Cf. A052984, A107839.
%K nonn,easy
%O 1,2
%A _Kevin Ryde_, Jan 04 2021