

A138159


Triangle read by rows: T(n,k) is the number of permutations of [n] having k occurrences of the pattern 321 (n>=1, 0<=k<=n(n1)(n2)/6).


1



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, 429, 429, 635, 461, 507, 395, 387, 320, 260, 232, 191, 162, 104, 130, 100, 24, 74, 62, 18, 32, 10, 30, 13, 8, 0, 10, 10, 0, 0, 0, 6, 0, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

(i) NoonanZeilberger 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(n1)(n2)/6 terms.
Sum of row n is n! (A000142).
T(n,0)=A000108(n) (the Catalan numbers).
T(n,1)=A003517(n1).
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.


REFERENCES

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, 607632. also Arxiv CO/0112092
Mansour, Toufik; Yan, Sherry H. F.; and Yang, Laura L. M.; Counting occurrences of 231 in an involution. Discrete Math. 306 (2006), 564572.
J. Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Math. 152 (1996), no. 13, 307313.
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, 381407.


LINKS

Table of n, a(n) for n=1..76.


FORMULA

The number of 321patterns 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).


EXAMPLE

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;


MAPLE

n:=9: with(combinat): P:=permute(n): f:=proc(k) local L: L:=proc(j) local ct, i: ct:=0: for i to j1 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*(n1)*(n2) 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*(n1)*(n2));


MATHEMATICA

ro[n_] := With[{}, P = Permutations[Range[n]]; f[k_] := With[{}, L[j_] := With[{}, ct = 0; Do[If[P[[k, j]] < P[[k, i]], ct = ct + 1], {i, 1, j  1}]; ct]; Sum[L[j]*(L[j] + P[[k, j]]  j), {j, 1, n}]]; a = Sort[Table[f[k], {k, 1, n!}]]; Do[c[h] = 0; Do[If[a[[m]] == h, c[h] = c[h] + 1], {m, 1, n!}], {h, 0, (1/6)*n*(n  1)*(n  2)}]; Table[c[h], {h, 0, (1/6)*n*(n  1)*(n  2)}]]; Flatten[Table[ro[n], {n, 1, 7}]] (* JeanFrançois Alcover, Sep 01 2011, after Maple *)


CROSSREFS

Cf. A000108, A003517, A001089, A001810.
Sequence in context: A114494 A118964 A073187 * A118919 A101282 A145879
Adjacent sequences: A138156 A138157 A138158 * A138160 A138161 A138162


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Mar 27 2008


STATUS

approved



