This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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(n-1)(n-2)/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(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). LINKS Alois P. Heinz, Rows n = 0..9, 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)); 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 Cf. A000108, A003517, A001089, A001810, A056986, A263771. Sequence in context: A118964 A263771 A073187 * A118919 A274404 A101282 Adjacent sequences:  A138156 A138157 A138158 * A138160 A138161 A138162 KEYWORD nonn,tabf AUTHOR Emeric Deutsch, Mar 27 2008 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.