1,2

(i) Noonan-Zeilberger item can be "linked"; (ii) Callan item can be linked (it occurs already in OEIS); (iii) Fulmek item is also in the ArXiv (CO/0112092). END

Row n has 1 + n(n-1)(n-2)/6 terms.

Sum of row n is n! (A000142).

T(n,0)=A000108(n) (the Catalan numbers).

T(n,1)=A003517(n-1).

T(n,2)=A001089(n).

Sum(k*T(n,k), k>=0)= A001810(n).

The given Maple program yields row 9 of the triangle; change the value of n to obtain other rows.

D. Callan, A recursive bijective approach to counting permutations...

M. Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. Appl. Math., 30, 2003, 607-632. also Arxiv CO/0112092

J. Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Math. 152 (1996), no. 1-3, 307-313.

J. Noonan and D. Zeilberger, [math/9808080] The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns.

J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of ``forbidden'' patterns, Adv. Appl. Math., 17, 1996, 381-407.

The number of 321-patterns of a given permutation p of [n] is given by Sum(L[i]R[i],i=1..n), where L (R) is the left (right) inversion vector of p. L and R are related by R[i]+i=p[i]+L[i] (the given Maple program makes use of this approach). References contain formulas and generating functions for the first few columns (some are only conjectured).

T(4,2)=3 because we have 4312, 4231 and 3421.

Triangle starts:

1;

2;

5,1;

14,6,3,0,1;

42,27,24,7,9,6,0,4,0,0,1;

132,110,133,70,74,54,37,32,24,12,16,6,6,8,0,0,5,0,0,0,1;

n:=9: with(combinat): P:=permute(n): f:=proc(k) local L: L:=proc(j) local ct, i: ct:=0: for i to j-1 do if P[k][j] < P[k][i] then ct:=ct+1 else end if end do: ct end proc: add(L(j)*(L(j)+P[k][j]-j), j=1..n) end proc: a:=sort([seq(f(k), k=1..factorial(n))]): for h from 0 to (1/6)*n*(n-1)*(n-2) do c[h]:=0: for m to factorial(n) do if a[m]=h then c[h]:=c[h]+1 else end if end do end do: seq(c[h], h=0..(1/6)*n*(n-1)*(n-2));

Cf. A000108, A003517, A001089, A001810.

Sequence in context: A114494 A118964 A073187 this_sequence A118919 A101282 A145879

Adjacent sequences: A138156 A138157 A138158 this_sequence A138160 A138161 A138162

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 27 2008