login
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
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
S. Klavzar, M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, MATCH Commun. Math. Comput. Chem., 68, 2012, 311-324.
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
Emeric Deutsch, Aug 18 2014
STATUS
approved