A245825 Triangle read by rows: T(n,k) is the number of the vertices of the Fibonacci cube G_n that have degree k (0<=k<=n).

1, 0, 2, 0, 2, 1, 0, 1, 3, 1, 0, 0, 5, 2, 1, 0, 0, 3, 7, 2, 1, 0, 0, 1, 10, 7, 2, 1, 0, 0, 0, 9, 14, 8, 2, 1, 0, 0, 0, 4, 23, 16, 9, 2, 1, 0, 0, 0, 1, 22, 34, 19, 10, 2, 1, 0, 0, 0, 0, 14, 50, 44, 22, 11, 2, 1, 0, 0, 0, 0, 5, 55, 77, 56, 25, 12, 2, 1, 0, 0, 0, 0, 1, 40, 117, 106, 69, 28, 13, 2, 1, 0, 0, 0, 0, 0, 20, 131, 188, 140, 83, 31, 14, 2, 1

Offset: 0

Author

Emeric Deutsch, Aug 03 2014

Keywords

• nonn
• tabl

Comments

The Fibonacci cube G_n is obtained from the n-cube Q_n by removing all the vertices that contain two consecutive 1s.

Sum of entries in row n is the Fibonacci number F_{n+2}.

Sum of entries in column k (k>=1) is the Fibonacci number F_{2k+3}. - Emeric Deutsch, Jun 22 2015

Sum(k*T(n,k), k=0..n) = 2*sum(F(k)*F(n+1-k),k=0..n+1) = 2*A001629(n+1).

Examples

			Row 2 is 0,2,1 because the Fibonacci cube G_2 is the path-tree P_3 having 2 vertices of degree 1 and 1 vertex of degree 2.
Triangle starts:
1;
0,2;
0,2,1;
0,1,3,1;
0,0,5,2,1;
0,0,3,7,2,1;
0,0,1,10,7,2,1;
		

Links

• S. Klavzar, M. Mollard, M. Petkovsek, The degree sequence of Fibonacci and Lucas cubes, Discrete Math., 311, 2011, 1310-1322.
• S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522

Crossrefs

Cf. A000045, A001519, A001629.

Programs

Maple

T := proc (n, k) options operator, arrow: sum(binomial(n-2*i, k-i)*binomial(i+1, n-k-i+1), i = 0 .. k) end proc: seq(seq(T(n, k), k = 0 .. n), n = 0 .. 13);

Formula

T(n,k) = sum(binomial(n-2i, k-i)*binomial(i+1,n-k-i+1), i=0..k).

G.f.: (1 + t*z + (1 - t)*t*z^2)/((1 - t*z)*(1 - t*z^2) - t*z^3).