A129714 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k runs (0<=k<=n). A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.

1, 0, 2, 0, 1, 2, 0, 1, 2, 2, 0, 1, 2, 3, 2, 0, 1, 2, 4, 4, 2, 0, 1, 2, 5, 6, 5, 2, 0, 1, 2, 6, 8, 9, 6, 2, 0, 1, 2, 7, 10, 14, 12, 7, 2, 0, 1, 2, 8, 12, 20, 20, 16, 8, 2, 0, 1, 2, 9, 14, 27, 30, 30, 20, 9, 2, 0, 1, 2, 10, 16, 35, 42, 50, 40, 25, 10, 2, 0, 1, 2, 11, 18, 44, 56, 77, 70, 55, 30, 11, 2

Offset: 0

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabl

Comments

Row sums are the Fibonacci numbers (A000045).

Examples

			T(5,3)=4 because we have 10111, 11011, 11101 and 01110.
Triangle starts:
  1;
  0,2;
  0,1,2;
  0,1,2,2;
  0,1,2,3,2;
  0,1,2,4,4,2;
		

Links

• M. Henk, J. Richter-Gebert and G. M. Ziegler, Basic properties of convex polytopes, Discrete and Computational Geometry, J.E. Goodman and J. O'Rourke eds., CRC Press, Boca Raton, Florida, 1997, Second Edition, 2004, 355-383.

Crossrefs

Cf. A000045, A065941, A073044, A129715.

Programs

Maple

T:=proc(n,k): if k<0 then 0 elif k=0 and n=0 then 1 elif k=0 then 0 elif n=1 and k=1 then 2 elif n=2 and k=1 then 1 elif n=2 and k=2 then 2 elif k>n then 0 else T(n-1,k)+T(n-2,k-2) fi end: for n from 0 to 14 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

Mathematica

T[n_, k_] := T[n, k] = Which[k < 0, 0, k == 0 && n == 0, 1, k == 0, 0, n == 1 && k == 1, 2, n == 2 && k == 1, 1, n == 2 && k == 2, 2, k > n, 0, True, T[n-1, k] + T[n-2, k-2]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 23 2024, after Maple program *)

Formula

T(n,k) = A073044(n,n-k) (since in each Fibonacci binary word of length n the number of runs plus the number of 11's is equal to n).

Sum_{k=0..n} k*T(n,k) = A129715(n).

G.f.: G(t,z)=(1+tz)(1-z+tz)/(1-z-t^2*z^2).

T(n,k) = T(n-1,k)+T(n-2,k-2) for n>=3, k>=1 (see the Maple program).

For n >=1, T(n+1,k+1) = binomial(n-floor((k+1)/2),floor(k/2)) + binomial(n-1-floor(k/2),floor((k-1)/2)) = A065941(n,k) + A065941(n-1,k-1). T(n+1,2k) = 2*binomial(n-k,k-1) and T(n+1,2k+1) = n/(n-k)*binomial(n-k,k). For 0 <= k < n and n >=1, T(n+1,k+1) equals the number of facets of the k-dimensional cyclic polytope C_k(n), defined as the convex hull of the n points (1,1^2,...,1^k),...,(n,n^2,...n^k) in R^k [see Henk et al., p.11]. [Peter Bala, Sep 25 2008]