A129713 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and starting with exactly k 1's (0<=k<=n). A Fibonacci binary word is a binary word having no 00 subword.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 5, 3, 2, 1, 1, 1, 8, 5, 3, 2, 1, 1, 1, 13, 8, 5, 3, 2, 1, 1, 1, 21, 13, 8, 5, 3, 2, 1, 1, 1, 34, 21, 13, 8, 5, 3, 2, 1, 1, 1, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 1, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 1, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 1, 233, 144

Offset: 0

Author

Emeric Deutsch, May 12 2007

Keywords

• nonn
• tabl
• easy

Comments

Row sums are the Fibonacci numbers (A000045). Sum(k*T(n,k), 0<=k<=n) = F(n+3)-2 = A001911(n).

Examples

			T(6,2) = 3 because we have 110110, 110111, 110101.
Triangle starts:
1;
1,1;
1,1,1;
2,1,1,1;
3,2,1,1,1;
5,3,2,1,1,1;
8,5,3,2,1,1,1;
		

Links

• Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

Crossrefs

Cf. A000045, A001911.

Cf. A054123.

Cf. A007298. - Altug Alkan, May 03 2016

Programs

Haskell

a129713 n k = a129713_tabl !! n !! k
a129713_row n = a129713_tabl !! n
a129713_tabl = [1] : [1, 1] : f [1] [1, 1] where
   f us vs = ws : f vs ws where
             ws = zipWith (+) (init us ++ [0, 0, 0]) (vs ++ [1])
-- Reinhard Zumkeller, May 26 2015

Maple

with(combinat): T:=proc(n,k) if k<=n-2 then fibonacci(n-k) elif k=n-1 or k=n then 1 else 0 fi end: for n from 0 to 15 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

Mathematica

nn=15;a=1/(1-y x);b=1/(1-x);Map[Select[#,#>0&]&,CoefficientList[Series[a (1+x)/(1-x^2b),{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Dec 04 2013 *)

Formula

T(n,k) = F(n-k) if k<=n-2, T(n,n-1) = T(n,n) = 1, where F(j) are the Fibonacci numbers (F(0)=0, F(1)=1). G.f.: G(t,z) = (1-z^2)/[(1-z-z^2)(1-tz)].

a(n) = A007298(n+4) - A007298(n+3). - Altug Alkan, May 03 2016