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

Author

Emeric Deutsch, Aug 10 2014

Keywords

• nonn
• easy

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.

Examples

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

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

Crossrefs

Cf. A000045, A000032, A001628, A001629.

Cf. A364605 (number of 6-cycles).

Programs

Magma

[((n-n^2)*Fibonacci(n) + (3*n^2 - 5*n)*Fibonacci(n-1))/10: n in [0..50]]; // Vincenzo Librandi, Aug 11 2014

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

PARI

concat([0,0,0,0], Vec(x^4*(x-2)/(x^2+x-1)^3 + O(x^100))) \\ Colin Barker, Aug 13 2014

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