login
Detour index of the n-hypercube graph.
1

%I #23 Apr 04 2019 10:35:26

%S 0,1,16,184,1744,15136,126016,1028224,8306944,66781696,535561216,

%T 4289726464,34338770944,274794029056,2198687727616,17590843899904,

%U 140732119711744,1125878432137216,9007113355657216,72057250441068544,576459377914937344

%N Detour index of the n-hypercube graph.

%C The longest path from a vertex to any other with the same parity will contain 2^n-2 edges and the longest path from a vertex to any other with opposite parity will contain 2^n-1 edges. This leads to a simple formula for the detour index. - _Andrew Howroyd_, Jun 19 2017

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DetourIndex.html">Detour Index</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (14,-56,64).

%F G.f.: x*(1 + 2*x + 16*x^2)/((1 - 2*x)*(1 - 4*x)*(1 - 8*x)). [Amended by _Bruno Berselli_, Apr 03 2019]

%F a(n) = 14*a(n-1) - 56*a(n-2) + 64*a(n-3).

%F a(n) = 2^n * (2^(2*n-1) - 5*2^(n-2) + 1) for n > 0. - _Andrew Howroyd_, Jun 19 2017

%F a(n) = A296819(2^n). - _Andrew Howroyd_, Dec 23 2017

%t LinearRecurrence[{14, -56, 64}, {0, 1, 16, 184}, 21] (* a(0)=0 amended by _Georg Fischer_, Apr 03 2019 *)

%Y Cf. A296778, A296819.

%K nonn,easy

%O 0,3

%A _Eric W. Weisstein_, Jun 13 2017

%E a(6)-a(20) from _Andrew Howroyd_, Jun 19 2017