login
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

%I #14 Aug 23 2024 10:48:38

%S 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,

%T 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,

%U 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

%N 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.

%C Row sums are the Fibonacci numbers (A000045).

%H M. Henk, J. Richter-Gebert and G. M. Ziegler, <a href="https://www.csun.edu/~ctoth/Handbook/chap15.pdf">Basic properties of convex polytopes</a>, Discrete and Computational Geometry, J.E. Goodman and J. O'Rourke eds., CRC Press, Boca Raton, Florida, 1997, Second Edition, 2004, 355-383.

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

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

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

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

%F 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]

%e T(5,3)=4 because we have 10111, 11011, 11101 and 01110.

%e Triangle starts:

%e 1;

%e 0,2;

%e 0,1,2;

%e 0,1,2,2;

%e 0,1,2,3,2;

%e 0,1,2,4,4,2;

%p 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

%t 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]];

%t Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 23 2024, after Maple program *)

%Y Cf. A000045, A065941, A073044, A129715.

%K nonn,tabl

%O 0,3

%A _Emeric Deutsch_, May 12 2007