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,3

Comments

Row sums are the Fibonacci numbers (A000045).

Links

Table of n, a(n) for n=0..90.

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.

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]

Example

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;

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

Crossrefs

Cf. A000045, A065941, A073044, A129715.

Sequence in context: A097203 A025850 A096771 * A022333 A055087 A025685

Adjacent sequences: A129711 A129712 A129713 * A129715 A129716 A129717

Keyword

nonn,tabl

Author

Emeric Deutsch, May 12 2007

Status

approved