A278136 - OEIS

%I #18 Jul 21 2019 06:49:50

%S 1,2,1,3,1,5,2,1,8,4,1,13,6,2,1,21,10,5,1,34,17,7,2,1,55,27,12,6,1,89,

%T 44,22,8,2,1,144,72,34,14,7,1,233,116,56,28,9,2,1,377,188,94,42,16,8,

%U 1,610,305,150,70,35,10,2,1,987,493,244,122,51,18,9,1

%N Triangle read by rows: T(n,k) is the maximum number of disjoint subgraphs of the Fibonacci cube Gamma(n) that are isomorphic to the hypercube of dimension k.

%C Number of entries in row n is 1 + ceiling(n/2).

%C T(n,0) = F(n+2) = A000045(n+2) (Fibonacci); number of vertices of Gamma(n).

%C Sum of entries in row n is A278137(n).

%C T(n,1) = floor(F(n+2)/2) (see Lemma 2.1 in the Gravier et al. paper).

%C The generating function of column k is x^{2k-1}/((1-x^3)^k*(1-x-x^2)) (k>=0) (see Corollary 2.5 in the Gravier et al. paper).

%H Indranil Ghosh, <a href="/A278136/b278136.txt">Rows 0..100, flattened</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.

%F T(n,k) = Sum_{i=k-1..floor((n+k-2)/3)} binomial(i,k-1)*F(n+k-3i-1), where F(j) = A000045(j) (Fibonacci); (see Corollary 2.4 in the Gravier et al. paper).

%F T(n,k) = T(n-2,k-1) + T(n-3,k) (n>=3, k>=1) (see Theorem 2.2 in the Gravier et al. paper).

%e Row 3 is 5,2,1. Indeed, the Fibonacci cube Gamma(3) has 5 vertices A, B, C, D, E and edges AB, BC, CD, DA, DE and so it has at most 2 disjoint edges and it has one square.

%e Triangle starts:

%e    1;

%e    2, 1;

%e    3, 1;

%e    5, 2, 1;

%e    8, 4, 1;

%e   13, 6, 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: for n from 0 to 20 do seq(T(n, k), k = 0 .. ceil((1/2)*n)) end do; # yields sequence in triangular form

%t Flatten[Table[Sum[Binomial[i,k-1] Fibonacci[n+k-3i-1], {i, k-1, Floor[(n+k-2)/3]}], {n,0,14},{k,0,Ceiling[n/2]}]] (* _Indranil Ghosh_, Mar 05 2017 *)

%Y Cf. A000045, A278137.

%K nonn,tabf

%O 0,2

%A _Emeric Deutsch_, Feb 26 2017