|
Search: id:A129707
|
|
|
| A129707 |
|
Number of inversions in all Fibonacci binary words of length n. A Fibonacci binary word is a binary word having no 00 subword. |
|
+0
3
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
a(n)=Sum(k*A129706(n,k), k>=0).
|
|
FORMULA
|
G.f.=z^2*(1+z)/(1-z-z^2)^3. Rec. rel:= a(n)=2a(n-1)+a(n-2)-2a(n-3)-a(n-4)+F(n), a(0)=a(1)=0,a(2)=1,a(3)=4
a(n-3) = ((5n^2-37n+50)*F(n-1) + 4(n-1)*F(n))/50 = (-1)^n*A055243(-n). - Peter Bala (pbala(AT)toucansurf.com), Oct 25 2007
|
|
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);
|
|
CROSSREFS
|
Cf. A129706.
Cf. A055243.
Sequence in context: A037255 A027658 A001982 this_sequence A133546 A005104 A028921
Adjacent sequences: A129704 A129705 A129706 this_sequence A129708 A129709 A129710
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), May 12 2007
|
|
|
Search completed in 0.002 seconds
|
