cp's OEIS Frontend

A340309 Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).

%I A340309 #12 Jan 14 2021 02:36:07
%S A340309 0,6,48,282,1476,7302,35016,164850,767340,3546366,16315248,74837802,
%T A340309 342621396,1566620022,7157423256,32682574050,149184117180,
%U A340309 680813718126,3106475197248,14173073072922,64659388538916,294971717255142,1345602571317096,6138257708432850
%N A340309 Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).
%C A340309 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 A340309 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 A340309 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 A340309 Kevin Ryde, <a href="/A340309/b340309.txt">Table of n, a(n) for n = 1..500</a>
%H A340309 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 A340309 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (8,-17,6).
%H A340309 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A340309 With P = (5 + sqrt(17))/2 = A082486, and M = (5 - sqrt(17))/2:
%F A340309 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 A340309 a(n) = (6/sqrt(17)) * Sum_{k=0..n-1} 3^k * (P^(n-1-k) - M^(n-1-k)) [Hinz et al.].
%F A340309 a(n) = 3*a(n-1) + 6*A107839(n-2), paths within and between subgraphs n-1.
%F A340309 a(n) = 8*a(n-1) - 17*a(n-2) + 6*a(n-3).
%F A340309 a(n) = (A052984(n) - 3^n)*3/2.
%F A340309 G.f.: 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x)).
%F A340309 G.f.: (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x).
%e A340309 For n=3 discs, the Hanoi graph is
%e A340309                 *           \
%e A340309                / \          | top
%e A340309               A---*         | subgraph,
%e A340309              /     \        | of n-1 = 2
%e A340309             B       *       | discs
%e A340309            / \     / \      |
%e A340309           C---D---E---*     /
%e A340309          /             \          two shortest
%e A340309         *               *           paths for
%e A340309        / \             / \           A to S
%e A340309       *---*           *---*          B to T
%e A340309      /     \         /     \         C to R
%e A340309     *       *       R       *        C to U
%e A340309    / \     / \     / \     / \       D to S
%e A340309   *---*---*---*---S---T---U---*
%e A340309 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 A340309 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 A340309 (PARI) my(p=Mod('x, 'x^2-5*'x+2)); a(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;
%Y A340309 Cf. A052984, A107839.
%K A340309 nonn,easy
%O A340309 1,2
%A A340309 _Kevin Ryde_, Jan 04 2021