|
| |
|
|
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
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Row sums are the Fibonacci numbers (A000045). 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*T(n,k), 0<=k<=n)=A129715(n).
|
|
|
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; [From Peter Bala, Sep 25 2008]
|
|
|
FORMULA
|
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]. [From 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
