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,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

Cf. A000032.

Sequence in context: A159914 A153251 A229167 * A109022 A023596 A208667

Adjacent sequences: A245965 A245966 A245967 * A245969 A245970 A245971

Keyword

nonn,easy

Author

Emeric Deutsch, Aug 16 2014

Status

approved