### Abstract

We give a recursive formula for the Moebius function of an interval $[\sigma,\pi]$ in the poset of permutations ordered by pattern containment in the case where $\pi$ 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 Moebius function in the case where $\sigma$ and $\pi$ 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. A consequence of the formula is that the Moebius function of such an interval $[\sigma,\pi]$ is bounded by the number of occurrences of $\sigma$ as a pattern in $\pi$. We also show that for any separable permutation $\pi$ the Moebius function of $(1,\pi)$ is either 0, 1 or -1.

Original language | English |
---|---|

Pages (from-to) | 2346–2364 |

Number of pages | 19 |

Journal | Journal of Combinatorial Theory Series A |

Volume | 118 |

Issue number | 8 |

DOIs | |

Publication status | Published - Nov 2011 |

### Keywords

- Möbius function
- poset
- permutations
- pattern containment

## Cite this

Burstein, A., Jelínek, V., Jelínková, E., & Steingrimsson, E. (2011). The Möbius function of separable and decomposable permutations.

*Journal of Combinatorial Theory Series A*,*118*(8), 2346–2364. https://doi.org/10.1016/j.jcta.2011.06.002