1,2

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)

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

G.f. A(x) satisfies: A(x) = (1-x)^2*A(x)^2 - x^2*A'(x). [From Paul D. Hanna (pauldhanna(AT)juno.com), Aug 02 2008]

(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=(1+x^2*deriv(A)/A)/(1-x)^2); polcoeff(A, n)} [From Paul D. Hanna (pauldhanna(AT)juno.com), Aug 02 2008]

Sequence in context: A148333 A122993 A137552 this_sequence A149881 A148334 A149882

Adjacent sequences: A137550 A137551 A137552 this_sequence A137554 A137555 A137556

nonn

Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Apr 25 2008