Sách Enumeration Schemes for Permutations Avoiding Barred Patterns

1 Introduction
Let q = q1


qm be a finite string of numbers. The reduction of q, denoted red(q), is
the string obtained by replacing the ith smallest letter(s) of q with i. For example, the
red(2674425) = 1452213. Given two permutations p ∈ Sn, q ∈ Sm, we say p contains q
as a pattern if there exist 1 6 i1 <


< im 6 n such that red(pi
1



pim ) = q. Otherwise
p avoids q. This definition of pattern avoidance appears in the characterization of 1-
stack sortable permutations [11] and the characterization of smooth Schubert varieties
[6]. Further, it introduces an interesting and well-studied enumeration problem; namely,
count the elements of the set Sn(Q) = { p ∈ Sn | p avoids q for all q ∈ Q} .
The focus of this paper is not the study Sn(Q), but a variation of pattern avoidance
given by the following definitions. Given q
, the barred permutation q
is the permutation obtained by copying the entries of q
and putting a bar over q
if and
only if bi = 1. Write Sm for the set of all barred permutations of length m. For example,