The Möbius function of separable and decomposable permutations☆

Publication year: 2011
Source: Journal of Combinatorial Theory, Series A, Volume 118, Issue 8, November 2011, Pages 2346-2364

Alexander, Burstein , Vít, Jelínek , Eva, Jelínková , Einar, Steingrímsson

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…