A245968 The edge independence number of the Lucas cube Lambda(n).

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

Offset: 0

Author

Emeric Deutsch, Aug 16 2014

Keywords

• nonn
• easy

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.

Examples

			a(3)=1 because Lambda(3) is the star tree on four vertices, having, obviously, vertex independence number equal to 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).

Crossrefs

Cf. A000032.

Programs

Magma

[Floor((Lucas(n)-1)/2):n in [0..50]]; // Vincenzo Librandi, Aug 31 2014

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 *)

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

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