A245961 - OEIS

%I #27 Jul 30 2023 09:04:22

%S 0,0,0,0,2,5,15,35,80,171,355,715,1410,2730,5208,9810,18280,33745,

%T 61785,112309,202840,364245,650705,1157015,2048532,3612900,6349200,

%U 11121300,19421150,33820061,58740915,101777495,175945280,303516015,522541903,897942115

%N Number of 4-cycles in the Lucas cube Lambda(n).

%C The vertex set of the Lucas cube Lambda(n) is the set of all binary strings of length n without consecutive 1's and without a 1 in the first and the last bit. Two vertices of the Lucas cube are adjacent if their strings differ in exactly one bit.

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

%H S. Klavzar, <a href="http://dx.doi.org/10.1016/j.disc.2004.02.023">On median nature and enumerative properties of Fibonacci-like cubes</a>, Discr. Math. 299 (2005), 145-153.

%H S. Klavzar, <a href="http://dx.doi.org/10.1007/s10878-011-9433-z">Structure of Fibonacci cubes: a survey</a>, J. Comb. Optim., 25, 2013, 505-522.

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

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

%F a(n) = ((n-n^2)*F(n) + (3n^2 - 5n)*F(n-1))/10, where F(n) = A000045(n), the Fibonacci numbers. Formula follows from Eq. (4) of the Klavzar 2005 reference and from the first formula on p. 511 of the Klavzar 2013 reference.

%F a(n) = Sum(L(i)*b(n-3-i), i=0..n-4), where L(i) = A000032(i) are the Lucas numbers and b(j) = A001629(j+1) is the number of edges in the Fibonacci cube Gamma(j) (see Prop. 9 of the Klavzar 2005 reference).

%F a(n) = 3*a(n-1)-5*a(n-3)+3*a(n-5)+a(n-6). G.f.: x^4*(x-2) / (x^2+x-1)^3. - _Colin Barker_, Aug 11 2014

%F a(n) = 2*A001628(n-4)-A001628(n-5). - _R. J. Mathar_, Jul 24 2022

%F G.f.: (-2+x)*x^4/(-1+x+x^2)^3. - _Eric W. Weisstein_, Jul 29 2023

%e a(3)=0 because the Lucas cube Lambda(3) is the star-tree on 4 vertices.

%p with(combinat): a := proc (n) options operator, arrow: (1/10)*n*(1-n)*fibonacci(n)+(1/10)*n*(3*n-5)*fibonacci(n-1) end proc: seq(a(n), n = 0 .. 35);

%t Table[((n - n^2) Fibonacci[n] + (3 n^2 - 5 n) Fibonacci[n - 1])/10, {n, 0, 50}] (* _Vincenzo Librandi_, Aug 11 2014 *)

%t LinearRecurrence[{3, 0, -5, 0, 3, 1}, {0, 0, 0, 2, 5, 15}, 20] (* _Eric W. Weisstein_, Jul 29 2023 *)

%t CoefficientList[Series[(-2 + x) x^3/(-1 + x + x^2)^3, {x, 0, 20}], x] (* _Eric W. Weisstein_, Jul 29 2023 *)

%o (Magma) [((n-n^2)*Fibonacci(n) + (3*n^2 - 5*n)*Fibonacci(n-1))/10: n in [0..50]]; // _Vincenzo Librandi_, Aug 11 2014

%o (PARI) concat([0,0,0,0], Vec(x^4*(x-2)/(x^2+x-1)^3 + O(x^100))) \\ _Colin Barker_, Aug 13 2014

%Y Cf. A000045, A000032, A001628, A001629.

%Y Cf. A364605 (number of 6-cycles).

%K nonn,easy

%O 0,5

%A _Emeric Deutsch_, Aug 10 2014