login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A278136 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. 2
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, 44, 22, 8, 2, 1, 144, 72, 34, 14, 7, 1, 233, 116, 56, 28, 9, 2, 1, 377, 188, 94, 42, 16, 8, 1, 610, 305, 150, 70, 35, 10, 2, 1, 987, 493, 244, 122, 51, 18, 9, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

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

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

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

LINKS

Indranil Ghosh, Rows 0..100, flattened

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.

FORMULA

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

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

EXAMPLE

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.

Triangle starts:

   1;

   2, 1;

   3, 1;

   5, 2, 1;

   8, 4, 1;

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

MATHEMATICA

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

CROSSREFS

Cf. A000045, A278137.

Sequence in context: A168018 A173238 A173284 * A085053 A296118 A296121

Adjacent sequences:  A278133 A278134 A278135 * A278137 A278138 A278139

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Feb 26 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 11:05 EDT 2019. Contains 328294 sequences. (Running on oeis4.)