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

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabf

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

Examples

			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;
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..10100 (rows 0 <= n <= 200, flattened.)

Crossrefs

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

Programs

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
				

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

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.