×

Twelve subsets of permutations enumerated as maximally clustered permutations. (English) Zbl 1399.05005

Summary: 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 \(S_n\) 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.

MSC:

05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices

Software:

OEIS