cp's OEIS Frontend

From Lara Pudwell, 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)

The number of permutations of length n avoiding the dashed pattern 1-42-3. - Andrew Baxter, May 17 2011

Apparently, also the number of permutations of length n avoiding the barred pattern 23{bar 1}54, which are the same as the permutations avoiding dashed pattern 1-24-3. - Andrew Baxter, May 17 2011

A partial order R is naturally labeled if xRy => x

A partial order is (2+2)-free if it does not contain an induced subposet that is isomorphic to the union of two disjoint 2-element chains.