Search: id:A117106
Results 1-1 of 1 results found.

%I A117106
%S A117106 1,2,6,23,104,530,2958,17734,112657,750726,5207910,37387881,276467208
%N A117106 Number of permutations in S_n avoiding 21{bar 3}54 (i.e. every occurrence 
               of 2154 is contained in an occurrence of a 21354).
%C A117106 Comment from Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Oct 23 2008 (Start):
%C A117106 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.
%C A117106 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.
%C A117106 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.
%C A117106 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)
%C A117106 The bar refers to a missing piece. In other words to say that a permutation 
               has the pattern 21{bar 3}54 means that it has a 2154 (or equivalently 
               a 2143) pattern but that there is no entry in the permutation so 
               that we can extend this 2154 to a 21543 pattern.
%H A117106 Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">
               Enumeration Schemes for Pattern-Avoiding Words and Permutations</
               a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H A117106 M. Bousquet-Melou and S. Butler, <a href="http://arXiv.org/abs/math.CO/
               0603617">Forest-like permutations</a>
%e A117106 a(4)=23 because the permutation 2143 has the pattern 21{bar 3}54, but 
               none of the other 23 permutations in S_4 do.
%Y A117106 Sequence in context: A005802 A061552 A053488 this_sequence A137534 A137535 
               A030266
%Y A117106 Adjacent sequences: A117103 A117104 A117105 this_sequence A117107 A117108 
               A117109
%K A117106 nonn
%O A117106 1,2
%A A117106 Steve Butler (sbutler(AT)math.ucsd.edu), Apr 18 2006

Search completed in 0.001 seconds