The Mِbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [ σ , π ] in the poset of permutations ordered by pattern containment in the case where π 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 Möbius function in the case where σ and π 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. o show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [ σ , π ] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of ( 1 , π ) is either 0, 1 or −1.