login
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.
3

%I #14 Sep 16 2017 17:20:02

%S 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,

%T 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,

%U 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

%N 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.

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

%H Reinhard Zumkeller, <a href="/A129713/b129713.txt">Rows n = 0..125 of triangle, flattened</a>

%F 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)].

%F a(n) = A007298(n+4) - A007298(n+3). - _Altug Alkan_, May 03 2016

%e T(6,2) = 3 because we have 110110, 110111, 110101.

%e Triangle starts:

%e 1;

%e 1,1;

%e 1,1,1;

%e 2,1,1,1;

%e 3,2,1,1,1;

%e 5,3,2,1,1,1;

%e 8,5,3,2,1,1,1;

%p 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

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

%o (Haskell)

%o a129713 n k = a129713_tabl !! n !! k

%o a129713_row n = a129713_tabl !! n

%o a129713_tabl = [1] : [1, 1] : f [1] [1, 1] where

%o f us vs = ws : f vs ws where

%o ws = zipWith (+) (init us ++ [0, 0, 0]) (vs ++ [1])

%o -- _Reinhard Zumkeller_, May 26 2015

%Y Cf. A000045, A001911.

%Y Cf. A054123.

%Y Cf. A007298. - _Altug Alkan_, May 03 2016

%K nonn,tabl,easy

%O 0,7

%A _Emeric Deutsch_, May 12 2007