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)

Also equals the row sums of triangle A131338, which starts with a '1' in row 0 and then for n>0 row n consists of n '1's followed by the partial sums of the prior row.

Also the number of permutations in S_n avoiding {bar 4}25{bar 1}3 (i.e. every occurrence of 253 is contained in an occurrence of a 42513). - Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Apr 25 2008 (See the Claesson-Dukes-Kitaev article)

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

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

Anders Claesson, Mark Dukes and Sergey Kitaev, Unlabeled (2+2)-free posets, ascent sequences and pattern avoiding permutations

a(n) = Sum_{k=0..n} C( (k+1)*(k+2)/2 + n-k-1, n-k).

(PARI) a(n)=sum(k=0, n, binomial((k+1)*(k+2)/2+n-k-1, n-k))

Cf. A098568, A131338.

Sequence in context: A035349 A155888 A006789 this_sequence A137549 A014327 A137550

Adjacent sequences: A098566 A098567 A098568 this_sequence A098570 A098571 A098572

nonn

Paul D. Hanna (pauldhanna(AT)juno.com), Sep 15 2004, Jun 29 2007