

A137534


Number of permutations in S_n avoiding 352{bar 4}1 (i.e., every occurrence of 3521 is contained in an occurrence of a 35241).


0



1, 2, 6, 23, 104, 530, 2959, 17757, 113000, 754981, 5255830, 37898152, 281717723, 2150636759, 16807757093
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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)


LINKS

Table of n, a(n) for n=1..15.
Lara Pudwell, Enumeration Schemes for PatternAvoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
L. Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.


CROSSREFS

Sequence in context: A053488 A338279 A117106 * A137535 A110447 A030266
Adjacent sequences: A137531 A137532 A137533 * A137535 A137536 A137537


KEYWORD

nonn,more


AUTHOR

Lara Pudwell, Apr 25 2008


EXTENSIONS

a(8)(15) from Lars Blomberg, Jun 04 2018


STATUS

approved



