|
|
A227713
|
|
The Wiener index of the tree g[n] (n>=0) defined recursively in the following manner: denoting by P[n] the path on n vertices, we define g[0] =P[2] while g[n] (n>=1) is the tree obtained by identifying the roots of 2 copies of g[n-1] and one of the end-vertices of P[n+1]; the root of g[n] is defined to be the other end-vertex of P[n+1].
|
|
1
|
|
|
1, 9, 90, 836, 6856, 49787, 326618, 1977322, 11244976, 60908337, 317509874, 1605448440, 7920487752, 38297112551, 182108066522, 853884638758, 3956279351760, 18143381822941, 82466719670866, 371917534537524, 1665777832832136, 7415146800493139
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Roughly speaking, g[4], for example, is obtained from the planted full binary tree of height 5 by replacing the edges at the levels 1,2,3,4 with paths of lengths 4, 3, 2, and 1, respectively.
The value of a(4) has been checked by the direct evaluation of the Wiener index (using Maple).
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (24,-254,1564,-6225,16820,-31496,40896,-36112,20672,-6912,1024).
|
|
FORMULA
|
a(n) = 80 +128*n/3 +19*n^2/2 +5*n^3/6 +2^n*(-64 +38*n +21*n^2/2 +3*n^3/2) +4^n*(-15 -27*n/2 +9*n^2/2).
G.f.: (1 -15*x +128*x^2 -602*x^3 +1801*x^4 -3968*x^5 +6016*x^6 -5528*x^7 +3120*x^8 -1344*x^9 +256*x^10) / ((1-x)^4*(1-2*x)^4*(1-4*x)^3).
|
|
EXAMPLE
|
a(1)=9 because g[1] is the tree in the shape of Y and 3*1 + 3*2 = 9.
|
|
MAPLE
|
a := proc (n) options operator, arrow: 80+(128/3)*n+(19/2)*n^2+(5/6)*n^3 +2^n*(-64+38*n +(21/2)*n^2+(3/2)*n^3)+4^n*(-15-(27/2)*n+(9/2)*n^2) end proc: seq(a(n), n = 0 .. 25);
|
|
PROG
|
(Magma) m:=25; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-15*x +128*x^2-602*x^3 +1801*x^4-3968*x^5+6016*x^6 -5528*x^7+3120*x^8 -1344*x^9 +256*x^10)/((1-x)^4*(1-2*x)^4*(1-4*x)^3))); // Bruno Berselli, Aug 08 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|