Seminar: Run-Sorted Permutations Avoiding Certain Patterns: The Case of Length 4 and Permutation Statistical Consequences
Speaker: Olivia Nabawanda, Mbarara University of Science and Technology, Uganda
Abstract: The study of pattern avoidance in permutations, particularly within the context of flattened partitions, has attracted considerable attention in recent years. Previous investigations enumerated flattened partitions over [n] that avoid single patterns or pairs of patterns of length three, revealing well-known counting sequences such as the Catalan numbers, powers of two, and Motzkin numbers. This work extends the analysis to patterns of length four in the setting of run-sorted permutations. The number of run-sorted permutations over [n] avoiding the patterns 1234, 1243, 1324, 1342, 1423, 1432, 3142, and 4132 is determined, with resulting sequences including the Catalan numbers, Motzkin numbers, and powers of two—sequences that also appear in the case of certain length-three patterns. A bijection is presented to highlight structural similarities among these patterns, enabling a generalization of the avoidance behavior for any pattern of length n ≥ 3 under this framework. This study, conducted jointly with Ronald Muhumuza, contributes to the understanding of the relationship between pattern avoidance and permutation statistics such as runs and inversions.
Keywords: Catalan number, flattened partition, permutation, Motzkin number, pattern, run