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

%I #28 Aug 01 2023 10:38:19

%S 0,0,1,1,3,5,8,14,23,37,61,99,160,260,421,681,1103,1785,2888,4674,

%T 7563,12237,19801,32039,51840,83880,135721,219601,355323,574925,

%U 930248,1505174,2435423,3940597,6376021,10316619,16692640,27009260,43701901,70711161,114413063

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

%C 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.

%H Vincenzo Librandi, <a href="/A245968/b245968.txt">Table of n, a(n) for n = 0..1000</a>

%H E. Munarini, C. P. Cippo, and N. Z. Salvi, <a href="http://www.fq.math.ca/Scanned/39-1/munarini.pdf">On the Lucas cubes</a>, The Fibonacci Quarterly, 39, No. 1, 2001, 12-21.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LucasCubeGraph.html">Lucas Cube Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MatchingNumber.html">Matching Number</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,-1,-1).

%F 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).

%F G.f.: x^2*(x^2+1) / ((x-1)*(x^2+x-1)*(x^2+x+1)). - _Colin Barker_, Aug 31 2014

%F a(n) = a(n-1)+a(n-2)+a(n-3)-a(n-4)-a(n-5). - _Colin Barker_, Aug 31 2014

%e a(3)=1 because Lambda(3) is the star tree on four vertices, having, obviously, vertex independence number equal to 1.

%p 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);

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

%t Floor[(LucasL[Range[20]] - 1)/2] (* _Eric W. Weisstein_, Aug 01 2023 *)

%t LinearRecurrence[{1, 1, 1, -1, -1}, {0, 1, 1, 3, 5, 8}, 20] (* _Eric W. Weisstein_, Aug 01 2023 *)

%t Table[LucasL[n]/2 - (Cos[2 n Pi/3] + 2)/3, {n, 20}] (* _Eric W. Weisstein_, Aug 01 2023 *)

%o (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

%o (Magma) [Floor((Lucas(n)-1)/2):n in [0..50]]; // _Vincenzo Librandi_, Aug 31 2014

%Y Cf. A000032.

%K nonn,easy

%O 0,5

%A _Emeric Deutsch_, Aug 16 2014