OFFSET
0,5
COMMENTS
The vertex set of the Lucas cube Lambda(n) is the set of all binary strings of length n without consecutive 1's and without a 1 in the first and the last bit. Two vertices of the Lucas cube are adjacent if their strings differ in exactly one bit.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Klavzar, On median nature and enumerative properties of Fibonacci-like cubes, Discr. Math. 299 (2005), 145-153.
S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522.
Eric Weisstein's World of Mathematics, Lucas Cube Graph
Index entries for linear recurrences with constant coefficients, signature (3,0,-5,0,3,1).
FORMULA
a(n) = ((n-n^2)*F(n) + (3n^2 - 5n)*F(n-1))/10, where F(n) = A000045(n), the Fibonacci numbers. Formula follows from Eq. (4) of the Klavzar 2005 reference and from the first formula on p. 511 of the Klavzar 2013 reference.
a(n) = Sum(L(i)*b(n-3-i), i=0..n-4), where L(i) = A000032(i) are the Lucas numbers and b(j) = A001629(j+1) is the number of edges in the Fibonacci cube Gamma(j) (see Prop. 9 of the Klavzar 2005 reference).
a(n) = 3*a(n-1)-5*a(n-3)+3*a(n-5)+a(n-6). G.f.: x^4*(x-2) / (x^2+x-1)^3. - Colin Barker, Aug 11 2014
G.f.: (-2+x)*x^4/(-1+x+x^2)^3. - Eric W. Weisstein, Jul 29 2023
EXAMPLE
a(3)=0 because the Lucas cube Lambda(3) is the star-tree on 4 vertices.
MAPLE
with(combinat): a := proc (n) options operator, arrow: (1/10)*n*(1-n)*fibonacci(n)+(1/10)*n*(3*n-5)*fibonacci(n-1) end proc: seq(a(n), n = 0 .. 35);
MATHEMATICA
Table[((n - n^2) Fibonacci[n] + (3 n^2 - 5 n) Fibonacci[n - 1])/10, {n, 0, 50}] (* Vincenzo Librandi, Aug 11 2014 *)
LinearRecurrence[{3, 0, -5, 0, 3, 1}, {0, 0, 0, 2, 5, 15}, 20] (* Eric W. Weisstein, Jul 29 2023 *)
CoefficientList[Series[(-2 + x) x^3/(-1 + x + x^2)^3, {x, 0, 20}], x] (* Eric W. Weisstein, Jul 29 2023 *)
PROG
(Magma) [((n-n^2)*Fibonacci(n) + (3*n^2 - 5*n)*Fibonacci(n-1))/10: n in [0..50]]; // Vincenzo Librandi, Aug 11 2014
(PARI) concat([0, 0, 0, 0], Vec(x^4*(x-2)/(x^2+x-1)^3 + O(x^100))) \\ Colin Barker, Aug 13 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Aug 10 2014
STATUS
approved