Pattern avoidance in compositions and multiset permutations

2005/04/14 by Carla D. Savage, Savage, Carla D., Herbert S. Wilf +1
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0504310

8 pages, no figure

arxiv created 2005/04/14 · arxiv updated 2009/12/01

Abstract

We study pattern avoidance by combinatorial objects other than permutations, namely by ordered partitions of an integer and by permutations of a multiset. In the former case we determine the generating function explicitly, for integer compositions of n that avoid a given pattern of length 3 and we show that the answer is the same for all such patterns. We also show that the number of multiset permutations that avoid a given three-letter pattern is the same for all such patterns, thereby extending and refining earlier results of Albert, Aldred et al., and by Atkinson, Walker and Linton. Further, the number of permutations of a multiset S, with a_i copies of i for i = 1, ..., k, that avoid a given permutation pattern in S₃ is a symmetric function of the a_i's, and we will give here a bijective proof of this fact first for the pattern (123), and then for all patterns in S₃ by using a recently discovered bijection of Amy N. Myers.

Related

• Pattern avoidance in compositions and powers of permutations
• Generalised Pattern Avoidance
• On restricted permutations on regular multisets
• Pattern Avoiding Permutations Enumerated by Inversions
• Counting Permutations that Avoid Many Patterns