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.
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
Offset: 0
Keywords
Examples
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.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216, 2015
- Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).
Crossrefs
Cf. A129714.
Programs
-
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 *)
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).
Comments