|
%I #31 Mar 28 2024 10:53:21
%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 <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
%O 0,4
%A _Emeric Deutsch_, May 12 2007
|
