|
|
A246174
|
|
Triangle read by rows: T(n,k) is the number of vertex pairs at distance k of the Lucas cube Lambda(n) (1<=k<=n).
|
|
1
|
|
|
2, 1, 3, 3, 8, 8, 4, 1, 15, 20, 15, 5, 30, 48, 44, 24, 6, 1, 56, 105, 119, 84, 35, 7, 104, 224, 296, 256, 144, 48, 8, 1, 189, 459, 696, 711, 495, 228, 63, 9, 340, 920, 1570, 1840, 1522, 880, 340, 80, 10, 1, 605, 1804, 3421, 4521, 4312, 2981, 1463, 484, 99, 11
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
The Lucas cube Lambda(n) can be defined as the graph whose vertices are the binary strings of length n without either two consecutive 1's or a 1 in the first and in the last position, and in which two vertices are adjacent when their Hamming distance is exactly 1.
The number of entries in row n is equal to n if n is even and equal to n-1 if n is odd.
The entries in row n are the coefficients of the Hosoya polynomial of the Lucas cube Lambda(n).
T(n,1) = A099920(n-1) = number of edges in Lambda(n).
Sum(kT(n,k), k>=1) = A238420(n) = the Wiener index of Lambda(n).
|
|
LINKS
|
E. Munarini, C. P. Cippo, N. Z. Salvi, On the Lucas cubes, The Fibonacci Quarterly, 39, No. 1, 2001, 12-21.
|
|
FORMULA
|
G.f.: tz^2(2+t-z+tz-3tz^2+tz^3+tz^4)/((1+tz)(1-z-tz-z^2-tz^2+tz^3)(1-z-z^2)). Derived from Theorem 4.3 of the Klavzar-Mollard reference in which the g.f. of the ordered Hosoya polynomials is given.
|
|
EXAMPLE
|
Row 2 is 2,1. Indeed, Lambda(2) is the path-tree P(3) having vertex-pair distances 1,1, and 2.
Triangle starts:
2,1;
3,3;
8,8,4,1;
15,20,15,5;
30,48,44,24,6,1;
|
|
MAPLE
|
g := t*z^2*(2+t-z+t*z-3*t*z^2+t*z^3+t*z^4)/((1+t*z)*(1-z-t*z-z^2-t*z^2+t*z^3)*(1-z-z^2)): gserz := simplify(series(g, z = 0, 20)): for j from 2 to 18 do H[j] := sort(coeff(gserz, z, j)) end do: for j from 2 to 13 do seq(coeff(H[j], t, k), k = 1 .. 2*floor((1/2)*j)) end do; # yields sequence in triangular form
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|