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
Examples
a(3)=4 because the Fibonacci words 110,111,101,010,011 have a total of 2 + 0 + 1 + 1 + 0 = 4 inversions.
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).
Programs
-
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 *) -
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 */
-
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
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
Comments