|
|
A288720
|
|
Detour index of the n-hypercube graph.
|
|
1
|
|
|
0, 1, 16, 184, 1744, 15136, 126016, 1028224, 8306944, 66781696, 535561216, 4289726464, 34338770944, 274794029056, 2198687727616, 17590843899904, 140732119711744, 1125878432137216, 9007113355657216, 72057250441068544, 576459377914937344
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
FORMULA
|
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]
a(n) = 14*a(n-1) - 56*a(n-2) + 64*a(n-3).
a(n) = 2^n * (2^(2*n-1) - 5*2^(n-2) + 1) for n > 0. - Andrew Howroyd, Jun 19 2017
|
|
MATHEMATICA
|
LinearRecurrence[{14, -56, 64}, {0, 1, 16, 184}, 21] (* a(0)=0 amended by Georg Fischer, Apr 03 2019 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|