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,2

Comments

a(n) = Sum(k*A129714(n,k), k=0..n).

a(n) = A241701(3n+1,n) for n>0. - Alois P. Heinz, Apr 27 2014

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).

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

Cf. A129714.

Sequence in context: A134508 A091357 A309950 * A024493 A130781 A352045

Adjacent sequences: A129712 A129713 A129714 * A129716 A129717 A129718

Keyword

nonn

Author

Emeric Deutsch, May 12 2007

Status

approved