A129707 - OEIS

%I #37 Nov 14 2024 15:18:24

%S 0,0,1,4,12,31,73,162,344,707,1416,2778,5358,10188,19139,35582,65556,

%T 119825,217487,392286,703618,1255669,2230608,3946020,6954060,12212280,

%U 21377365,37309288,64935132,112726771,195224773,337343034,581700476

%N Number of inversions in all Fibonacci binary words of length n.

%C A Fibonacci binary word is a binary word having no 00 subword.

%H Michael De Vlieger, <a href="/A129707/b129707.txt">Table of n, a(n) for n = 0..4754</a>

%H Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, <a href="https://arxiv.org/abs/2403.15053">On certain Fibonacci representations</a>, arXiv:2403.15053 [math.NT], 2024. See p. 2.

%H Tamás Szakács, <a href="https://hdl.handle.net/2437/381856">Linear recursive sequences and factorials</a>, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 2.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-5,0,3,1).

%F a(n) = Sum_{k>=0} k*A129706(n,k).

%F G.f.: z^2*(1+z)/(1-z-z^2)^3.

%F 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.

%F 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

%F a(n) = A001628(n-3) + A001628(n-2). - _R. J. Mathar_, Dec 07 2011

%F a(n+1) = A123585(n+2,n). - _Philippe Deléham_, Dec 18 2011

%F a(n) = Sum_{k=floor((n-1)/2)..n-1}  k*(k+1)/2*C(k,n-k-1). - _Vladimir Kruchinin_, Sep 17 2020

%e a(3)=4 because the Fibonacci words 110,111,101,010,011 have a total of 2 + 0 + 1 + 1 + 0 = 4 inversions.

%p 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);

%t CoefficientList[Series[x^2*(1 + x)/(1 - x - x^2)^3, {x,0,50}], x] (* _G. C. Greubel_, Mar 04 2017 *)

%o (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

%o (Maxima)

%o a(n) = sum(k*(k+1)*binomial(k,n-k-1),k,floor((n-1)/2),n-1)/2; /* _Vladimir Kruchinin_, Sep 17 2020 */

%Y Cf. A129706.

%Y Cf. A055243.

%K nonn,easy

%O 0,4

%A _Emeric Deutsch_, May 12 2007