login
A129717
Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 101's (n >= 0, 0 <= k <= floor((n-1)/2)). A Fibonacci binary word is a binary word having no 00 subword.
2
1, 2, 3, 4, 1, 4, 4, 4, 8, 1, 4, 12, 5, 4, 16, 13, 1, 4, 20, 25, 6, 4, 24, 41, 19, 1, 4, 28, 61, 44, 7, 4, 32, 85, 85, 26, 1, 4, 36, 113, 146, 70, 8, 4, 40, 145, 231, 155, 34, 1, 4, 44, 181, 344, 301, 104, 9, 4, 48, 221, 489, 532, 259, 43, 1, 4, 52, 265, 670, 876, 560, 147, 10, 4, 56
OFFSET
0,2
COMMENTS
Row n has 1+floor((n-1)/2) terms for n >= 1.
Row sums are the Fibonacci numbers (A000045).
T(n,1) = A008574(n-3).
T(n,2) = A001844(n-5).
T(n,3) = A005900(n-6).
T(n,4) = A006325(n-7).
T(n,5) = A033455(n-10).
T(n,k) = A129718(n,k+1) (since in each word: 1 + the number of 101's = number of runs of 1's).
Sum_{k>=0} k*T(n,k) = A004798(n-2).
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..10100 (rows 0 <= n <= 200, flattened.)
FORMULA
G.f.: G(t,z) = (1+z)*(1 + z^2 - t*z^2)/(1 - z - t*z^2).
G.f. of col 0: (1+z)(1+z^2)/(1-z), leading to the partial sums of 1,1,1,1,0,0,0,...
G.f. of col k: z^(2k+1)*(1+z)^2/(1-z)^(k+1) (k >= 1).
T(n,k) = binomial(n-k-1, k) + 2*binomial(n-k-2, k) + binomial(n-k-3, k) for n >= 4 and 0 <= k < n/2.
EXAMPLE
T(6,2)=5 because we have 110101, 101101, 101010, 101011 and 010101.
Triangle starts:
1;
2;
3;
4, 1;
4, 4;
4, 8, 1;
4, 12, 5;
MAPLE
T:=proc(n, k) if n=0 and k=0 then 1 elif n=1 and k=0 then 2 elif n=2 and k=0 then 3 elif n=3 and k=1 then 1 elif k<n/2 then binomial(n-k-1, k)+2*binomial(n-k-2, k)+binomial(n-k-3, k) else 0 fi end: 1; for n from 1 to 18 do seq(T(n, k), k=0..floor(n-1)/2) od; # yields sequence in triangular form
MATHEMATICA
MapAt[{0, 1} + # &, #, 4] /. {} -> {1} &@ Table[If[n < 3, n + 1, Binomial[n - k - 1, k] + 2 Binomial[n - k - 2, k] + Binomial[n - k - 3, k]], {n, 0, 17}, {k, 0, Floor[(n - 1)/2]}] // Flatten (* Michael De Vlieger, Nov 15 2019 *)
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 12 2007
STATUS
approved