cp's OEIS Frontend

A129715 Number of runs in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.

%I A129715 #16 Nov 09 2022 13:31:59
%S A129715 0,2,5,11,22,43,81,150,273,491,874,1543,2705,4714,8173,14107,24254,
%T A129715 41555,70977,120894,205401,348187,589010,994511,1676257,2820818,
%U A129715 4739861,7953515,13328998,22310971,37304049,62307558,103968225,173324939
%N A129715 Number of runs in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.
%C A129715 a(n) = Sum(k*A129714(n,k), k=0..n).
%C A129715 a(n) = A241701(3n+1,n) for n>0. - _Alois P. Heinz_, Apr 27 2014
%H A129715 Vincenzo Librandi, <a href="/A129715/b129715.txt">Table of n, a(n) for n = 0..1000</a>
%H A129715 W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216, 2015
%H A129715 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F A129715 G.f.: z(2+z-z^2-z^3)/(1-z-z^2)^2. Rec. rel.: a(n)=a(n-1)+a(n-2)+2F(n) for n>=3, where F(n) is a Fibonacci number (F(0)=0,F(1)=1).
%e A129715 a(3)=11 because in the Fibonacci binary words 011, 111, 101, 010 and 110 we have a total of 2+1+3+3+2=11 runs.
%p A129715 with(combinat): a[0]:=0: a[1]:=2: a[2]:=5: for n from 3 to 40 do a[n]:=a[n-1]+a[n-2]+2*fibonacci(n) od: seq(a[n],n=0..40);
%t A129715 CoefficientList[Series[x (2 + x - x^2 - x^3)/(1 - x - x^2)^2, {x, 0, 30}], x] (* _Vincenzo Librandi_, Apr 28 2014 *)
%t A129715 LinearRecurrence[{2,1,-2,-1},{0,2,5,11,22},40] (* _Harvey P. Dale_, Nov 09 2022 *)
%Y A129715 Cf. A129714.
%K A129715 nonn
%O A129715 0,2
%A A129715 _Emeric Deutsch_, May 12 2007