Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #14 Nov 10 2024 14:26:50
%S 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,
%T 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,
%U 0,1,0,0,0,0,11,66,55,44,11,11,0,1
%N 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).
%C 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.
%C 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.
%C Sum(k*T(n,k), k=0..n) = 2*n*F(n-1) = 2*A099920(n-1).
%H S. Klavzar, M. Mollard, M. Petkovsek, <a href="http://dx.doi.org/10.1016/j.disc.2011.03.019">The degree sequence of Fibonacci and Lucas cubes</a>, Discrete Math., 311, 2011, 1310-1322.
%H S. Klavzar, <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/FibonacciCubesRevised.pdf">Structure of Fibonacci cubes: a survey</a>, preprint.
%H S. Klavzar, <a href="http://dx.doi.org/10.1007/s10878-011-9433-z">Structure of Fibonacci cubes: a survey</a>, J. Comb. Optim., 25, 2013, 505-522
%F 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).
%F 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.
%e 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.
%e 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.
%e Triangle starts:
%e 1;
%e 1,0;
%e 0,2,1;
%e 0,3,0,1;
%e 0,0,6,0,1;
%e 0,0,5,5,0,1;
%p 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
%Y Cf. A000045, A099920.
%K nonn,tabl
%O 0,5
%A _Emeric Deutsch_, Aug 08 2014