Nhảy đến nội dung

Twelve subsets of permutations enumerated as maximally clustered permutations


David Callana, Toufik Mansourb, Mark Shattuck*

Source title: 
Annales Mathematicae et Informaticae, 47: 41-74, 2017 (Scopus)
Academic year of acceptance: 

The problem of avoiding a single pattern or a pair of patterns of length four by permutations has been well studied. Less is known about the avoidance of three 4-letter patterns. In this paper, we show that the number of members of Sn avoiding any one of twelve triples of 4-letter patterns is given by sequence A129775 in OEIS, which is known to count maximally clustered permutations. Numerical evidence confirms that there are no other (non-trivial) triples of 4-letter patterns giving rise to this sequence and hence one obtains the largest (4, 4, 4)-Wilf-equivalence class for permutations. We make use of a variety of methods in proving our result, including recurrences, the kernel method, direct counting, and bijections.