A129710 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 01 subwords (0 <= k <= floor(n/2)). A Fibonacci binary word is a binary word having no 00 subword.

1, 2, 2, 1, 2, 3, 2, 5, 1, 2, 7, 4, 2, 9, 9, 1, 2, 11, 16, 5, 2, 13, 25, 14, 1, 2, 15, 36, 30, 6, 2, 17, 49, 55, 20, 1, 2, 19, 64, 91, 50, 7, 2, 21, 81, 140, 105, 27, 1, 2, 23, 100, 204, 196, 77, 8, 2, 25, 121, 285, 336, 182, 35, 1, 2, 27, 144, 385, 540, 378, 112, 9, 2, 29, 169, 506

Offset: 0

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabf

Comments

Also number of Fibonacci binary words of length n and having k 10 subwords.

Row n has 1+floor(n/2) terms.

Row sums are the Fibonacci numbers (A000045).

T(n,0)=2 for n >= 1.

Sum_{k>=0} k*T(n,k) = A023610(n-2).

Triangle, with zeros omitted, given by (2, -1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 1/2, -1/2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Jan 14 2012

Riordan array ((1+x)/(1-x), x^2/(1-x)), zeros omitted. - Philippe Deléham, Jan 14 2012

Examples

			T(5,2)=4 because we have 10101, 01101, 01010 and 01011.
Triangle starts:
  1;
  2;
  2, 1;
  2, 3;
  2, 5, 1;
  2, 7, 4;
  2, 9, 9, 1;
Triangle (2, -1, 0, 0, 0, 0, 0, ...) DELTA (0, 1/2, -1/2, 0, 0, 0, 0, 0, 0, ...) begins:
  1;
  2, 0;
  2, 1, 0;
  2, 3, 0, 0;
  2, 5, 1, 0, 0;
  2, 7, 4, 0, 0, 0;
  2, 9, 9, 1, 0, 0, 0;
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..10200 (rows 0 <= n <= 200, flattened.)
• Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
• Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.

Crossrefs

Cf. A000045, A023610.

Cf. A029635, A029653.

Columns: A040000, A005408, A000290, A000330, A002415, A005585, A040977, A050486, A053347, A054333, A054334, A057788.

Programs

Maple

T:=proc(n,k) if n=0 and k=0 then 1 elif k<=floor(n/2) then binomial(n-k,k)+binomial(n-k-1,k) else 0 fi end: for n from 0 to 18 do seq(T(n,k),k=0..floor(n/2)) od; # yields sequence in triangular form

Mathematica

MapAt[# - 1 &, #, 1] &@ Table[Binomial[n - k, k] + Binomial[n - k - 1, k], {n, 0, 16}, {k, 0, Floor[n/2]}] // Flatten (* Michael De Vlieger, Nov 15 2019 *)

Formula

T(n,k) = binomial(n-k,k) + binomial(n-k-1,k) for n >= 1 and 0 <= k <= floor(n/2).

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

Sum_{k=0..n} T(n,k)*x^k = (-1)^n*A078050(n), A057079(n), A040000(n), A000045(n+2), A000079(n), A006138(n), A026597(n), A133407(n), A133467(n), A133469(n), A133479(n), A133558(n), A133577(n), A063092(n) for x = -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 respectively. - Philippe Deléham, Jan 14 2012

T(n,k) = T(n-1,k) + T(n-2,k-1) with T(0,0)=1, T(1,0)=2, T(1,1)=0 and T(n,k) = 0 if k > n or if k < 0. - Philippe Deléham, Jan 14 2012