

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).


4



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, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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).


LINKS

Alois P. Heinz, Rows n = 0..9, flattened
D. Callan, A recursive bijective approach to counting permutations containing 3letter patterns, arXiv:math/0211380 [math.CO], 2002.
FindStat  Combinatorial Statistic Finder, The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3
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.
Toufik Mansour, Sherry H. F. Yan and Laura L. M. Yang, Counting occurrences of 231 in an involution, Discrete Mathematics 306 (2006), pages 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, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998.
J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of "forbidden" patterns, Adv. Appl. Math., 17, 1996, 381407.


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;
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

# The following Maple program yields row 9 of the triangle; change the value of n to obtain other rows.
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, A056986, A263771.
Sequence in context: A118964 A263771 A073187 * A118919 A101282 A263776
Adjacent sequences: A138156 A138157 A138158 * A138160 A138161 A138162


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Mar 27 2008


STATUS

approved



