Journal of Combinatorics

Volume 5 (2014)

Number 4

Pattern avoidance in the rook monoid

Pages: 471 – 497

DOI: https://dx.doi.org/10.4310/JOC.2014.v5.n4.a5

Authors

Daniel Daly (Department of Mathematics, Southeast Missouri State University, Cape Girardeau, Missouri, U.S.A.)

Lara Pudwell (Department of Mathematics and Statistics, Valparaiso University, Valparaiso, Indiana, U.S.A.)

Abstract

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.

Keywords

pattern avoidance, rook monoid, enumeration schemes

Published 11 March 2015