The M?bius function of separable and decomposable permutations*Jelinek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education

摘要

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.We also 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.