|
|
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.
|
|
3
|
|
|
0, 2, 5, 11, 22, 43, 81, 150, 273, 491, 874, 1543, 2705, 4714, 8173, 14107, 24254, 41555, 70977, 120894, 205401, 348187, 589010, 994511, 1676257, 2820818, 4739861, 7953515, 13328998, 22310971, 37304049, 62307558, 103968225, 173324939
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n) = Sum(k*A129714(n,k), k=0..n).
|
|
LINKS
|
|
|
FORMULA
|
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).
|
|
EXAMPLE
|
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.
|
|
MAPLE
|
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);
|
|
MATHEMATICA
|
CoefficientList[Series[x (2 + x - x^2 - x^3)/(1 - x - x^2)^2, {x, 0, 30}], x] (*Vincenzo Librandi,Apr 28 2014 *)
LinearRecurrence[{2, 1, -2, -1}, {0, 2, 5, 11, 22}, 40] (*Harvey P. Dale,Nov 09 2022 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|