OFFSET
0,4
COMMENTS
A Fibonacci binary word is a binary word having no 00 subword.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..4754
Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, On certain Fibonacci representations, arXiv:2403.15053 [math.NT], 2024. See p. 2.
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 2.
Index entries for linear recurrences with constant coefficients, signature (3,0,-5,0,3,1).
FORMULA
a(n) = Sum_{k>=0} k*A129706(n,k).
G.f.: z^2*(1+z)/(1-z-z^2)^3.
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4) + F(n), a(0)=a(1)=0, a(2)=1, a(3)=4.
a(n-3) = ((5*n^2 - 37*n + 50)*F(n-1) + 4*(n-1)*F(n))/50 = (-1)^n*A055243(-n). - Peter Bala, Oct 25 2007
a(n+1) = A123585(n+2,n). - Philippe Deléham, Dec 18 2011
a(n) = Sum_{k=floor((n-1)/2)..n-1} k*(k+1)/2*C(k,n-k-1). - Vladimir Kruchinin, Sep 17 2020
EXAMPLE
a(3)=4 because the Fibonacci words 110,111,101,010,011 have a total of 2 + 0 + 1 + 1 + 0 = 4 inversions.
MAPLE
with(combinat): a[0]:=0: a[1]:=0: a[2]:=1: a[3]:=4: for n from 4 to 40 do a[n]:=2*a[n-1]+a[n-2]-2*a[n-3]-a[n-4]+fibonacci(n) od: seq(a[n], n=0..40);
MATHEMATICA
CoefficientList[Series[x^2*(1 + x)/(1 - x - x^2)^3, {x, 0, 50}], x] (* G. C. Greubel, Mar 04 2017 *)
PROG
(PARI) x='x+O('x^50); concat([0, 0], Vec(x^2*(1 + x)/(1 - x - x^2)^3)) \\ G. C. Greubel, Mar 04 2017
(Maxima)
a(n) = sum(k*(k+1)*binomial(k, n-k-1), k, floor((n-1)/2), n-1)/2; /* Vladimir Kruchinin, Sep 17 2020 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, May 12 2007
STATUS
approved