×

Enumeration schemes for permutations avoiding barred patterns. (English) Zbl 1215.05006

Summary: We give the first comprehensive collection of enumeration results for permutations that avoid barred patterns of length \(\leq 4\). We then use the method of prefix enumeration schemes to find recurrences counting permutations that avoid a barred pattern of length \(> 4\) or a set of barred patterns.

MSC:

05A05 Permutations, words, matrices

Software:

InsEnc; OEIS

Online Encyclopedia of Integer Sequences:

Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.
Antidiagonal sums of nexus numbers (A047969).
a(0)=1; thereafter, a(m+1) = Sum_{k=0..m} k!*a(m-k).
Row sums of the triangle of triangular binomial coefficients given by A098568.
Number of permutations containing 3241 patterns only as part of 35241 patterns.
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).
Expansion of g.f.: A(x) = Product_{n>=0} 1/( 1 - x/(1-x)^n )^( 1/2^(n+1) ).
Number of permutations in S_n avoiding {bar 1}432 (i.e., every occurrence of 432 is contained in an occurrence of a 1432).
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).
Number of permutations in S_n avoiding 1{bar 4}235 (i.e., every occurrence of 1235 is contained in an occurrence of a 14235).
Number of permutations in S_n avoiding {bar 4}2153 (i.e., every occurrence of 2153 is contained in an occurrence of a 42153).
Number of permutations in S_n avoiding 5134{bar 2} (i.e., every occurrence of 5134 is contained in an occurrence of a 51342).
Number of permutations in S_n avoiding 25{bar 1}34 (i.e., every occurrence of 2534 is contained in an occurrence of a 25134).
Number of permutations in S_n avoiding 1{bar 5}324 (i.e., every occurrence of 1324 is contained in an occurrence of a 15324).
Number of permutations in S_n avoiding {bar 4}1253 (i.e., every occurrence of 1253 is contained in an occurrence of a 41253).
Number of permutations in S_n avoiding 1{bar 5}234 (i.e., every occurrence of 1234 is contained in an occurrence of a 15234).
Number of permutations in S_n avoiding {bar 1}3425 (i.e., every occurrence of 3425 is contained in an occurrence of a 13425).
Number of permutations in S_n avoiding {bar 1}3245 (i.e., every occurrence of 3245 is contained in an occurrence of a 13245).
Number of permutations in S_n avoiding {bar 5}1342 (i.e., every occurrence of 1342 is contained in an occurrence of a 51342).
Number of permutations in S_n avoiding {bar 5}2143 (i.e., every occurrence of 2143 is contained in an occurrence of a 52143).
Number of permutations in S_n avoiding 5234{bar 1} (i.e., every occurrence of 5234 is contained in an occurrence of a 52341).
Number of permutations in S_n avoiding {bar 5}1243 (i.e., every occurrence of 1243 is contained in an occurrence of a 51243).
Number of permutations in S_n avoiding {bar 5}1234 (i.e., every occurrence of 1234 is contained in an occurrence of a 51234).
Number of permutations in S_n avoiding 5{bar 1}{bar 2}43 (i.e., every occurrence of 543 is contained in an occurrence of a 51243).
Number of permutations in S_n avoiding 31{bar 5}{bar 4}2 (i.e., every occurrence of 312 is contained in an occurrence of a 31542).
Number of permutations in S_n avoiding {bar 2}413{bar 5} (i.e., every occurrence of 413 is contained in an occurrence of a 24135).
Number of permutations in S_n avoiding {bar 1}5{bar 2}43 (i.e., every occurrence of 543 is contained in an occurrence of 15243).
Number of permutations in S_n avoiding {bar 5}{bar 4}231 (i.e., every occurrence of 231 is contained in an occurrence of a 54231).
Number of permutations in S_n avoiding {bar 5}{bar 4}132 (i.e., every occurrence of 132 is contained in an occurrence of a 54132).
Number of permutations in S_n avoiding {bar 4}{bar 5}123 (i.e., every occurrence of 123 is contained in an occurrence of a 45123).
Number of permutations in S_n avoiding {bar 1}432{bar 5} (i.e., every occurrence of 432 is contained in an occurrence of a 14325).
Number of permutations in S_n avoiding 345{bar 2}{bar 1} (i.e., every occurrence of 345 is contained in an occurrence of a 34521).
Number of permutations that avoid the barred pattern bar{1}43bar{5}2.