OFFSET
0,5
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.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
E. Munarini, C. P. Cippo, and N. Z. Salvi, On the Lucas cubes, The Fibonacci Quarterly, 39, No. 1, 2001, 12-21.
Eric Weisstein's World of Mathematics, Lucas Cube Graph
Eric Weisstein's World of Mathematics, Matching Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1,-1).
FORMULA
a(n) = floor((L(n)-1)/2), where L(n) = A000032(n) are the Lucas numbers (L(0)=2, L(1)=1, L(n)=L(n-1)+L(n-2) for n>=2).
G.f.: x^2*(x^2+1) / ((x-1)*(x^2+x-1)*(x^2+x+1)). - Colin Barker, Aug 31 2014
a(n) = a(n-1)+a(n-2)+a(n-3)-a(n-4)-a(n-5). - Colin Barker, Aug 31 2014
EXAMPLE
a(3)=1 because Lambda(3) is the star tree on four vertices, having, obviously, vertex independence number equal to 1.
MAPLE
with(combinat): a := proc (n) options operator, arrow: floor((1/2)*fibonacci(n+1)+(1/2)*fibonacci(n-1)-1/2) end proc: seq(a(n), n = 0 .. 40);
MATHEMATICA
CoefficientList[Series[x^2 (x^2 + 1)/((x - 1) (x^2 + x - 1) (x^2 + x + 1)), {x, 0, 50}], x] (* Vincenzo Librandi, Aug 31 2014 *)
Floor[(LucasL[Range[20]] - 1)/2] (* Eric W. Weisstein, Aug 01 2023 *)
LinearRecurrence[{1, 1, 1, -1, -1}, {0, 1, 1, 3, 5, 8}, 20] (* Eric W. Weisstein, Aug 01 2023 *)
Table[LucasL[n]/2 - (Cos[2 n Pi/3] + 2)/3, {n, 20}] (* Eric W. Weisstein, Aug 01 2023 *)
PROG
(PARI) concat([0, 0], Vec(x^2*(x^2+1)/((x-1)*(x^2+x-1)*(x^2+x+1)) + O(x^100))) \\ Colin Barker, Aug 31 2014
(Magma) [Floor((Lucas(n)-1)/2):n in [0..50]]; // Vincenzo Librandi, Aug 31 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Aug 16 2014
STATUS
approved