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,2

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

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.

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

Example

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;

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

Crossrefs

Cf. A000045, A023610.

Cf. A029635, A029653.

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

Sequence in context: A263073 A133091 A112204 * A298857 A070680 A351524

Adjacent sequences: A129707 A129708 A129709 * A129711 A129712 A129713

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved