|
| |
|
|
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).
|
|
0
| |
|
|
1, 2, 6, 23, 104, 530, 2958, 17734, 112657, 750726, 5207910, 37387881, 276467208
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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)
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.
|
|
|
LINKS
| Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
M. Bousquet-Melou and S. Butler, Forest-like permutations
|
|
|
FORMULA
| It appears that a(n) = ((-432-120*n^2-360*n)*A005258(n)+(-120*n+144+120*n^3)*A005258(n+1)) / (5*(n-1)*n^2*(n+2)^2*(n+3)^2*(n+4)), for n>1. - Mark van Hoeij, Oct 24 2011
It appears that G.f. is: -(p*(x^4-78*x^3-1606*x^2+78*x+1)*hypergeom([1/12, 5/12],[1],1728*x^5*(1-11*x-x^2)/p^3)-(x^4+18*x^3+74*x^2-18*x+1)*(228*x-228*x^3+494*x^2+x^4+1)*hypergeom([5/12, 13/12],[1],1728*x^5*(1-11*x-x^2)/p^3))*(x^2+1)/(720*x^4*p^(5/4)) - (1+8*x-6*x^2+7*x^3)/(5*x^3) where p = 1-12*x+14*x^2+12*x^3+x^4 - Mark van Hoeij, Oct 25 2011
|
|
|
EXAMPLE
| 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.
|
|
|
CROSSREFS
| Sequence in context: A005802 A061552 A053488 * A137534 A137535 A030266
Adjacent sequences: A117103 A117104 A117105 * A117107 A117108 A117109
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Steve Butler (sbutler(AT)math.ucsd.edu), Apr 18 2006
|
| |
|
|
