OFFSET
0,3
COMMENTS
LINKS
Alois P. Heinz, Rows n = 0..15, flattened
D. Callan, A recursive bijective approach to counting permutations containing 3-letter 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, 607-632. 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 564-572.
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, 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, 381-407.
FORMULA
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).
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 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));
# second Maple program:
b:= proc(s, c) option remember; (n-> `if`(n=0, x^c, add(b(s minus {j},
(t-> (j-n+t)*t+c)(nops(select(x-> x>j, s)))), j=s)))(nops(s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..9); # Alois P. Heinz, Dec 01 2021
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}]] (* Jean-François Alcover, Sep 01 2011, after Maple *)
CROSSREFS
KEYWORD
AUTHOR
Emeric Deutsch, Mar 27 2008
STATUS
approved