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.

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

Crossrefs

Cf. A000045, A008574, A001844, A005900, A006325, A033455, A129718, A004798.

Sequence in context: A363130 A325242 A257053 * A317088 A276380 A352724

Adjacent sequences: A129714 A129715 A129716 * A129718 A129719 A129720

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved