A278137 Maximum number of disjoint subgraphs of the Fibonacci cube Gamma(n) that are isomorphic to the hypercube of dimension k, summed over all k.

1, 3, 4, 8, 13, 22, 37, 61, 101, 166, 272, 445, 726, 1183, 1925, 3129, 5082, 8248, 13379, 21692, 35157, 56963, 92271, 149434, 241970, 391755, 634190, 1026561, 1661567, 2689209, 4352208, 7043314, 11398035, 18444678, 29847123, 48297643, 78152505, 126460400

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

S. Gravier, M. Mollard, S. Spacapan, S. S. Zemljic, On disjoint hypercubes in Fibonacci cubes, Discrete Appl. Math., 190-191, 2015, 50-55.

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

M. Mollard, Maximal hypercubes in Fibonacci and Lucas cubes, Discrete Appl. Math., 160, 2012, 2479-2483.

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

Formula

a(n) = a(n-2) + a(n-3) + 2*F(n), where F(n) = A000045(n) (Fibonacci); a(0)=1, a(1)=3, a(2)=4; follows from Theorem 2.2 of the Gravier et al. paper.

a(n) = Sum(A278136(n,k), k>=0).

From Colin Barker, Feb 26 2017: (Start)

a(n) = a(n-1) + 2*a(n-2) - 2*a(n-4) - a(n-5) for n>4.

G.f.: (1 + 2*x - x^2 - 2*x^3 - x^4) / ((1 - x - x^2)*(1 - x^2 - x^3)).

(End)

a(n) = 2*A000045(n+2)-A000931(n+6). - R. J. Mathar, Jul 24 2022

Example

a(3) = 8; indeed, row 3 of A278136 is 5,2,1.

Maple

with(combinat): F := proc (k) options operator, arrow; fibonacci(k) end proc: T := proc (n, k) options operator, arrow: sum(binomial(i, k-1)*F(n+k-3*i-1), i = k-1 .. floor((1/3)*n+(1/3)*k-2/3)) end proc: seq(add(T(n, k), k = 0 .. ceil((1/2)*n)), n = 0 .. 45);
with(combinat): a := proc (n) if n = 0 then 1 elif n = 1 then 3 elif n = 2 then 4 else a(n-2)+a(n-3)+2*fibonacci(n) end if end proc: seq(a(n), n = 0 .. 45);

Prog

(PARI) Vec((1 + 2*x - x^2 - 2*x^3 - x^4) / ((1 - x - x^2)*(1 - x^2 - x^3)) + O(x^40)) \\ Colin Barker, Feb 27 2017

Crossrefs

Cf. A000045, A278136.

Sequence in context: A049720 A078172 A022308 * A349977 A206268 A178749

Adjacent sequences: A278134 A278135 A278136 * A278138 A278139 A278140

Keyword

nonn,easy

Author

Emeric Deutsch, Feb 26 2017

Status

approved