|
|
A245968
|
|
The edge independence number of the Lucas cube Lambda(n).
|
|
1
|
|
|
0, 0, 1, 1, 3, 5, 8, 14, 23, 37, 61, 99, 160, 260, 421, 681, 1103, 1785, 2888, 4674, 7563, 12237, 19801, 32039, 51840, 83880, 135721, 219601, 355323, 574925, 930248, 1505174, 2435423, 3940597, 6376021, 10316619, 16692640, 27009260, 43701901, 70711161, 114413063
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
E. Munarini, C. P. Cippo, and N. Z. Salvi, On the Lucas cubes, The Fibonacci Quarterly, 39, No. 1, 2001, 12-21.
|
|
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 *)
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|