A129707 Number of inversions in all Fibonacci binary words of length n.

0, 0, 1, 4, 12, 31, 73, 162, 344, 707, 1416, 2778, 5358, 10188, 19139, 35582, 65556, 119825, 217487, 392286, 703618, 1255669, 2230608, 3946020, 6954060, 12212280, 21377365, 37309288, 64935132, 112726771, 195224773, 337343034, 581700476

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.

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) = A001628(n-3) + A001628(n-2). - R. J. Mathar, Dec 07 2011

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

Cf. A129706.

Cf. A055243.

Sequence in context: A037255 A027658 A001982 * A320545 A232580 A133546

Adjacent sequences: A129704 A129705 A129706 * A129708 A129709 A129710

Keyword

nonn

Author

Emeric Deutsch, May 12 2007

Status

approved