Journal of Combinatorics
Volume 5 (2014)
Pattern avoidance in the rook monoid
Pages: 471 – 497
We consider two types of pattern avoidance in the rook monoid, i.e. the set of 0–1 square matrices with at most one nonzero entry in each row and each column. For one-dimensional rook patterns, we completely characterize monoid elements avoiding a single pattern of length at most three and develop an enumeration scheme algorithm to study rook placements avoiding sets of patterns.
pattern avoidance, rook monoid, enumeration schemes