A short note on the Stanley-Wilf Conjecture for permutations on multisets

Abstract

The concept of pattern avoidance respectively containment in permutations can be extended to permutations on multisets in a straightforward way. In this note we present a direct proof of the already known fact that the well-known Stanley-Wilf Conjecture, stating that the number of permutations avoiding a given pattern does not grow faster than exponentially, also holds for permutations on multisets.

arXiv commentThe contents of this paper have been integrated in the more comprehensive paper "On restricted permutations on regular multisets", http://arxiv.org/abs/1306.4781