A129706 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k inversions (n>=0, 0<=k<=floor(n(n+1)/6)). A Fibonacci binary word is a binary word having no 00 subword.

1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 4, 2, 1, 2, 2, 2, 4, 4, 4, 2, 1, 2, 2, 2, 4, 4, 6, 6, 4, 2, 2, 2, 2, 2, 4, 4, 6, 8, 8, 6, 6, 4, 2, 1, 2, 2, 2, 4, 4, 6, 8, 10, 10, 10, 10, 8, 6, 4, 2, 1, 2, 2, 2, 4, 4, 6, 8, 10, 12, 14, 14, 14, 14, 12, 10, 8, 4, 2, 2, 2, 2, 2, 4, 4, 6, 8, 10, 12, 16, 18, 18, 20

Offset

0,2

Comments

Row n has 1+floor(n(n+1)/6) terms. Row sums are the Fibonacci numbers (A000045). Sum(k*T(n,k), k>=0)=A129707(n).

Links

Table of n, a(n) for n=0..95.

Formula

G.f.=G(t,z)=H(t,1,z), where H(t,x,z)=1+z+xzH(t,x,z)+txz^2*H(t,tx,z). Row generating polynomials P[n] are given by P[n](t)=Q[n](t,1), where Q[0]=1, Q[1]=1+x, Q[n](t,x)=xQ[n-1](t,x)+txQ[n-2](t,tx) for n>=2.

Example

T(5,3)=4 because we have 11101, 10101, 01110 and 01010.
Triangle starts:
1;
2;
2,1;
2,2,1;
2,2,2,2;
2,2,2,4,2,1;
2,2,2,4,4,4,2,1;

Maple

Q[0]:=1: Q[1]:=1+x: for n from 2 to 12 do Q[n]:=expand(x*Q[n-1]+t*x*subs(x=t*x, Q[n-2])) od: for n from 0 to 15 do P[n]:=sort(subs(x=1, Q[n])) od: for n from 0 to 12 do seq(coeff(P[n], t, j), j=0..floor(n*(n+1)/6)) od; # yields sequence in triangular form

Crossrefs

Cf. A000045, A129707.

Sequence in context: A119646 A024693 A025126 * A160384 A178305 A338621

Adjacent sequences: A129703 A129704 A129705 * A129707 A129708 A129709

Keyword

nonn,tabf

Author

Emeric Deutsch, May 12 2007

Status

approved