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

0, 0, 0, 0, 2, 5, 15, 35, 80, 171, 355, 715, 1410, 2730, 5208, 9810, 18280, 33745, 61785, 112309, 202840, 364245, 650705, 1157015, 2048532, 3612900, 6349200, 11121300, 19421150, 33820061, 58740915, 101777495, 175945280, 303516015, 522541903, 897942115

Offset

0,5

Comments

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.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

S. Klavzar, On median nature and enumerative properties of Fibonacci-like cubes, Discr. Math. 299 (2005), 145-153.

S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522.

Eric Weisstein's World of Mathematics, Lucas Cube Graph

Index entries for linear recurrences with constant coefficients, signature (3,0,-5,0,3,1).

Formula

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.

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

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

a(n) = 2*A001628(n-4)-A001628(n-5). - R. J. Mathar, Jul 24 2022

G.f.: (-2+x)*x^4/(-1+x+x^2)^3. - Eric W. Weisstein, Jul 29 2023

Example

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

Maple

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

Mathematica

Table[((n - n^2) Fibonacci[n] + (3 n^2 - 5 n) Fibonacci[n - 1])/10, {n, 0, 50}] (* Vincenzo Librandi, Aug 11 2014 *)
LinearRecurrence[{3, 0, -5, 0, 3, 1}, {0, 0, 0, 2, 5, 15}, 20] (* Eric W. Weisstein, Jul 29 2023 *)
CoefficientList[Series[(-2 + x) x^3/(-1 + x + x^2)^3, {x, 0, 20}], x] (* Eric W. Weisstein, Jul 29 2023 *)

Prog

(Magma) [((n-n^2)*Fibonacci(n) + (3*n^2 - 5*n)*Fibonacci(n-1))/10: n in [0..50]]; // Vincenzo Librandi, Aug 11 2014
(PARI) concat([0, 0, 0, 0], Vec(x^4*(x-2)/(x^2+x-1)^3 + O(x^100))) \\ Colin Barker, Aug 13 2014

Crossrefs

Cf. A000045, A000032, A001628, A001629.

Cf. A364605 (number of 6-cycles).

Sequence in context: A226103 A000962 A118387 * A034522 A276720 A148339

Adjacent sequences: A245958 A245959 A245960 * A245962 A245963 A245964

Keyword

nonn,easy

Author

Emeric Deutsch, Aug 10 2014

Status

approved