|
|
A192017
|
|
Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the Fibonacci tree of order n (1<=k<=n; entries in row n are the coefficients of the corresponding Wiener polynomial).
|
|
0
|
|
|
1, 2, 1, 4, 4, 2, 7, 10, 9, 2, 12, 21, 27, 15, 3, 20, 40, 65, 57, 25, 3, 33, 72, 138, 163, 114, 37, 4, 54, 125, 270, 394, 378, 206, 54, 4, 88, 212, 500, 854, 1033, 796, 354, 74, 5, 143, 354, 891, 1716, 2479, 2463, 1571, 574, 100, 5, 232, 585, 1545, 3265, 5424, 6559, 5469, 2917, 896, 130, 6
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The Fibonacci trees f(k) of order k are defined as follows: 1. f(-1) and f(0) each consist of a single node. 2. For k>=1, to the root of f(k-1), taken as the root of f(k), we attach with a rightmost edge the tree f(k-2). See the Iyer & Reddy references. These trees are not the same as the Fibonacci trees in A180566.
Sum of entries in row n is A191797(n+2).
|
|
REFERENCES
|
K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of Binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.
|
|
LINKS
|
|
|
FORMULA
|
T(n,1) = A000071(n-2) (Fibonacci numbers minus 1).
Sum_{k=1..n} k*T(n,k) = A165910(n) (the Wiener indices).
The Wiener polynomial w(n,t) of the Fibonacci tree of order n satisfies the recurrence relation w(n,t) = w(n-1,t) + w(n-2,t) + t*r(n-1,t)*r(n-2,t), w(0,t)=w(1,t)=0, where r(n,t) is the generating polynomial of the nodes of the Fibonacci tree of order n with respect to the level of the nodes (for example, r(2,t) = 1 + 2t for the tree /\; see A011973 and the Maple program).
|
|
EXAMPLE
|
T(2,2)=1 because in the Fibonacci tree of order 2, namely /\, there is only 1 pair of nodes at distance 2 (the two leaves).
Triangle starts:
1;
2, 1;
4, 4, 2;
7, 10, 9, 2;
12, 21, 27, 15, 3;
20, 40, 65, 57, 25, 3;
|
|
MAPLE
|
G := (1+t*z)/(1-z-t*z^2): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 11 do r[n] := sort(coeff(Gser, z, n)) end do; w[0] := 0; w[1] := t; for n from 2 to 11 do w[n] := sort(expand(w[n-1]+w[n-2]+t*r[n-1]*r[n-2])) end do: for n from 1 to 11 do seq(coeff(w[n], t, j), j = 1 .. n) end do; # yields sequence in triangular form
|
|
MATHEMATICA
|
m = 11; Gser = Series[(1 + t*z)/(1 - z - t*z^2), {z, 0, m}]; Do[r[n] = Coefficient[Gser, z, n], {n, 0, m}]; w[0] = 0; w[1] = t; Do[w[n] = Expand[w[n - 1] + w[n - 2] + t*r[n - 1]*r[n - 2]] , {n, 2, m}]; Flatten[Table[Coefficient[w[n], t, j], {n, 1, m}, {j, 1, n}]] (* Jean-François Alcover, Sep 02 2011, after Maple *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|