login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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

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, 607-632. 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), 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, [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.

LINKS

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

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;

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

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

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

Content is available under The OEIS End-User License Agreement .

Last modified April 24 10:01 EDT 2014. Contains 240965 sequences.