A278137 - OEIS

%I #17 Jul 24 2022 12:27:09

%S 1,3,4,8,13,22,37,61,101,166,272,445,726,1183,1925,3129,5082,8248,

%T 13379,21692,35157,56963,92271,149434,241970,391755,634190,1026561,

%U 1661567,2689209,4352208,7043314,11398035,18444678,29847123,48297643,78152505,126460400

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

%H Colin Barker, <a href="/A278137/b278137.txt">Table of n, a(n) for n = 0..1000</a>

%H S. Gravier, M. Mollard, S. Spacapan, S. S. Zemljic, <a href="http://dx.doi.org/10.1016/j.dam.2015.03.016">On disjoint hypercubes in Fibonacci cubes</a>, Discrete Appl. Math., 190-191, 2015, 50-55.

%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 M. Mollard, <a href="http://dx.doi.org/10.1016/j.dam.2012.06.003">Maximal hypercubes in Fibonacci and Lucas cubes</a>, Discrete Appl. Math., 160, 2012, 2479-2483.

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

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

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

%F From _Colin Barker_, Feb 26 2017: (Start)

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

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

%F (End)

%F a(n) = 2*A000045(n+2)-A000931(n+6). - _R. J. Mathar_, Jul 24 2022

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

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

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

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

%Y Cf. A000045, A278136.

%K nonn,easy

%O 0,2

%A _Emeric Deutsch_, Feb 26 2017