
COMMENTS

From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is orderisomorphic 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)


EXAMPLE

a(5) = 104: There are 16 permutations that have a 5234 *pattern* that is not followed by a 1. This is different from looking for the string 5234 followed by 1.
A 5234 pattern is a string of 4 numbers abcd where b<c<d<a (i.e. the string has the same relative order as the numbers 5234.)
The 16 permutations that have a 5234 pattern not followed by an even smaller number are:
{[1, 5, 2, 3, 4], [2, 5, 1, 3, 4], [3, 5, 1, 2, 4], [4, 1, 2, 3, 5], [4, 1, 2, 5, 3], [4, 1, 5, 2, 3], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4], [5, 1, 2, 4, 3], [5, 1, 3, 2, 4], [5, 1, 3, 4, 2], [5, 1, 4, 2, 3], [5, 2, 1, 3, 4], [5, 2, 3, 1, 4], [5, 3, 1, 2, 4], [5, 4, 1, 2, 3]}
For example, in 25134, 5134 forms a 5234 pattern that is not followed by something even smaller.
