Publication at Faculty of Mathematics and Physics |
2010
Abstract
A permutation is separable if it avoids the patterns 2413 and 3142. 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.