# The Möbius function of separable and decomposable permutations

Burstein, Alexander and Jelínek, Vít and Jelínková, Eva and Steingrimsson, Einar
(2011)
*The Möbius function of separable and decomposable permutations.*
Journal of Combinatorial Theory Series A, 118 (8).
2346–2364.

Preview |
PDF
mobius.pdf Preprint Download (400kB)| Preview |

## Abstract

We give a recursive formula for the Moebius function of an interval $[\sigma,\pi]$ in the poset of permutations ordered by pattern containment in the case where $\pi$ is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1, 2, ..., k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Moebius function in the case where $\sigma$ and $\pi$ are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. A consequence of the formula is that the Moebius function of such an interval $[\sigma,\pi]$ is bounded by the number of occurrences of $\sigma$ as a pattern in $\pi$. We also show that for any separable permutation $\pi$ the Moebius function of $(1,\pi)$ is either 0, 1 or -1.

#### ORCID iDs

Burstein, Alexander, Jelínek, Vít, Jelínková, Eva and Steingrimsson, Einar ORCID: https://orcid.org/0000-0003-4611-0849;Item type: Article ID code: 33802 Dates: DateEventNovember 2011PublishedKeywords: Möbius function , poset , permutations, pattern containment, Electronic computers. Computer science, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, Theoretical Computer Science Subjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 19 Oct 2011 15:40 Last modified: 29 Jan 2021 02:03 URI: https://strathprints.strath.ac.uk/id/eprint/33802