Authors: Vít Jelínek ¹; Eva Jelínková ²; Einar Steingrímsson ¹

• 1 Institute of Mathematics
• 2 Department of Applied Mathematics (KAM)

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. Using the notion of separating tree, we give a computationally efficient formula for the Möbius function of an interval $(q,p)$ in the poset of separable permutations ordered by pattern containment. A consequence of the formula is that the Möbius function of such an interval $(q,p)$ is bounded by the number of occurrences of $q$ as a pattern in $p$. The formula also implies that for any separable permutation $p$ the Möbius function of $(1,p)$ is either 0, 1 or -1.