A245960 Triangle read by rows: T(n,k) is the number of the vertices of the Lucas cube H_n having degree k (0<=k<=n).

1, 1, 0, 0, 2, 1, 0, 3, 0, 1, 0, 0, 6, 0, 1, 0, 0, 5, 5, 0, 1, 0, 0, 3, 8, 6, 0, 1, 0, 0, 0, 14, 7, 7, 0, 1, 0, 0, 0, 8, 22, 8, 8, 0, 1, 0, 0, 0, 3, 27, 27, 9, 9, 0, 1, 0, 0, 0, 0, 25, 42, 35, 10, 10, 0, 1, 0, 0, 0, 0, 11, 66, 55, 44, 11, 11, 0, 1

Offset: 0

Author

Emeric Deutsch, Aug 08 2014

Keywords

• nonn
• tabl

Comments

The vertex set of the Lucas cube H_n is the set of all binary strings of length n without consecutive 1's and without strings that start and end with 1. Two vertices are adjacent if their strings differ in exactly one bit.

Sum of entries in row n (n>=1) is the Lucas number L(n) = F(n-1)+F(n+1), where F(n) = A000045(n) are the Fibonacci numbers.

Sum(k*T(n,k), k=0..n) = 2*n*F(n-1) = 2*A099920(n-1).

Examples

			Row 2 is 0,2,1 because the Lucas cube H_2 is  the path-tree P_3 having 2 vertices of degree 1 and 1 vertex of degree 2.
Row 3 is 0,3,0,1 because the Lucas cube H_3 is the star tree with 4 vertices; the vertex degrees are 1, 1, 1, and 3.
Triangle starts:
  1;
  1,0;
  0,2,1;
  0,3,0,1;
  0,0,6,0,1;
  0,0,5,5,0,1;
		

Links

• S. Klavzar, M. Mollard, M. Petkovsek, The degree sequence of Fibonacci and Lucas cubes, Discrete Math., 311, 2011, 1310-1322.
• S. Klavzar, Structure of Fibonacci cubes: a survey, preprint.
• S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522

Crossrefs

Cf. A000045, A099920.

Programs

Maple

G := (1+(1-t)*z+z^2*t^2+(1-t)*z^3*t-(1-t)^2*z^4*t)/((1-t*z)*(1-z^2*t)-z^3*t): Gserz := simplify(series(G, z = 0, 20)): T := proc (n, k) options operator, arrow: coeff(coeff(Gserz, z, n), t, k) end proc: for n from 0 to 15 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

Formula

G.f.: (1+(1-t)*z+t^2*z^2+(1-t)*t*z^3-t*(1-t)^2*z^4)/((1-t*z)*(1-t*z^2)-t*z^3).

If n>=2 then T(n,k) = sum(2*binomial(i,2i+k-n)*binomial(n-2i-1,k-i)+binomial(i-1,2i+k-n)*binomial(n-2i,k-i), i=0..k). Recall that binomial(m,k)=0 if k<0.