A129715 - OEIS

%I #16 Nov 09 2022 13:31:59

%S 0,2,5,11,22,43,81,150,273,491,874,1543,2705,4714,8173,14107,24254,

%T 41555,70977,120894,205401,348187,589010,994511,1676257,2820818,

%U 4739861,7953515,13328998,22310971,37304049,62307558,103968225,173324939

%N 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 a(n) = Sum(k*A129714(n,k), k=0..n).

%C a(n) = A241701(3n+1,n) for n>0. - _Alois P. Heinz_, Apr 27 2014

%H Vincenzo Librandi, <a href="/A129715/b129715.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).

%F 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 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 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 CoefficientList[Series[x (2 + x - x^2 - x^3)/(1 - x - x^2)^2, {x, 0, 30}], x] (* _Vincenzo Librandi_, Apr 28 2014 *)

%t LinearRecurrence[{2,1,-2,-1},{0,2,5,11,22},40] (* _Harvey P. Dale_, Nov 09 2022 *)

%Y Cf. A129714.

%K nonn

%O 0,2

%A _Emeric Deutsch_, May 12 2007