0,6

T(n,k) is the number of 321-avoiding permutations of {1,2,...,n} having inversion number equal to k. Example: T(4,2)=5 because we have 1423, 1342, 3124, 2143 and 2341.

Row n has 1+floor(n^2/4) entries.

Row sums are the Catalan numbers (A000108).

Sum(k*T(n,k), k>=0)=A008549(n-1).

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, Journal of Difference Equations and Applications, 5, 1999, 435-490.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Some permutations with forbidden subsequences and their inversion number, Discrete Math., 234, 2001, 1-15.

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see section 5).

G.f.=G(t,z)=H(t,1/t,z), where H(t,x,z)=1+zH(t,x,z)[H(t,tx,z)-1+tx] (H(t,x,z) is the trivariate g.f. of Dyck paths with respect to semilength, sum of peak-heights and number of peaks, marked by z, t and x, respectively).

T(4,2)=5 because we have UDUUDUDD (5-3=2), UDUUUDD (4-2=2), UUDDUUDD (4-2=2), UUDUDDUD (5-3=2) and UUUDDDUD (4-2=2); here U=(1,1), D=(1,-1).

Triangle starts:

1;

1;

1,1;

1,2,2;

1,3,5,4,1;

1,4,9,12,10,4,2;

1,5,14,25,31,26,16,9,4,1;

H:=1/(1+z-t*x*z-z*h[1]): for n to 13 do h[n]:=1/(1+z-x*t^(n+1)*z-z*h[n+1]) end do: G:=subs({h[11]=0, x=1/t}, H): Gser:=simplify(series(G, z=0, 12)): for n from 0 to 9 do P[n]:=sort(coeff(Gser, z, n)) end do: for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..floor((1/4)*n^2)) end do; # yields sequence in triangular form

Cf. A000108, A008549, A129183.

Sequence in context: A106198 A054336 A079956 this_sequence A026300 A099514 A139687

Adjacent sequences: A140714 A140715 A140716 this_sequence A140718 A140719 A140720

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 08 2008