0,3

Comment from Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Oct 23 2008 (Start):

A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a<c<b.

Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.

A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.

For example, if q=5{bar 1}32{bar 4}, then q1=532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b<d<c<e<a. (End)

Apparently, also the number of permutations in S_n avoiding {bar 1}43{bar 5}2 (i.e. every occurrence of 432 is contained in an occurrence of a 14352). - Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Apr 25 2008

Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.

A(x) = (1-x)^(-1/2) * (1 - x/(1-x))^(-1/4) * (1 - x/(1-x)^2)^(-1/8) * (1 - x/(1-x)^3)^(-1/16) * ...

(PARI) {a(n)=round(polcoeff(prod(i=0, 6*n+10, 1/(1-x/(1-x)^i +x*O(x^n))^(1/2^(i+1))), n))}

(PARI) {a(n)=local(A); if(n<0, 0, A=1+O(x); for(k=1, n, A=truncate(A)+x*O(x^k); A+=substvec(A, [x, y], [x/(1-x*y+O(x^k)), y*(1-x*y)]) -A^2*(1-x)); subst(polcoeff(A, n), y, 1))} /* Michael Somos Oct 21 2006 */

Cf. A122992.

Sequence in context: A137551 A160701 A148333 this_sequence A137552 A137553 A149881

Adjacent sequences: A122990 A122991 A122992 this_sequence A122994 A122995 A122996

nonn

Paul D. Hanna (pauldhanna(AT)juno.com), Sep 23 2006